Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-03-15 Dutch Flag

posted Mar 15, 2018, 10:18 AM by Konstantinovich Samuel
Goal Dutch Flag partitioning.

 An array of ints that contains many 0's, 1's and 2's.

Modify the array such that all the 0's come before all the 1's which before all the 2's.

Do this in linear time!

we need to keep track of an extra index between the old i and j.

Before i was the boundary for less than values, and j was the boundary for greater than values. 

let us name our indices 

lt  ->  less-than boundary
gt -> greater-than boundary
i  ->  unknown boundary

index:             lt              i                    gt           
regions:      r1           r2               r3               r4

r1 are less than the pivot
r2 are equal to the pivot
r3 are UNKNOWN! 
r4 are greater than the pivot