Skip to content

Instantly share code, notes, and snippets.

@sdpatil
Created August 13, 2017 23:40
Show Gist options
  • Save sdpatil/6eefa17bc6d00d0c364feabeebfc6da3 to your computer and use it in GitHub Desktop.
Save sdpatil/6eefa17bc6d00d0c364feabeebfc6da3 to your computer and use it in GitHub Desktop.
Dutch National Flag Problem/Can reach end
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Problem: Write a program that takes an array A and index i into A, and rearranges the elements such that all elements
* less than A[i] pivot appear first, followed by elements equal to pivot, followed by elements equal to pivot
*/
public class DutchNationalFlag {
public static void main(String[] argv) {
List<Color> flags = new ArrayList();
flags.add(Color.RED);
flags.add(Color.BLUE);
flags.add(Color.WHITE);
flags.add(Color.RED);
flags.add(Color.BLUE);
flags.add(Color.WHITE);
flags.add(Color.WHITE);
System.out.println(flags);
dutchFlagPartition(5, flags);
System.out.println(flags);
}
/**
* Given color
* [RED, BLUE, WHITE, RED, BLUE, WHITE, WHITE] sort it to
* [RED, RED, WHITE, WHITE, WHITE, BLUE, BLUE]
* There are 3 buckets so split it like that
*/
public static void dutchFlagPartition(int pivotIndex, List<Color> A) {
Color partition = A.get(pivotIndex);
int smaller = 0;
int equal = 0 ;
int larger = A.size()-1;
while (equal <larger){
if(A.get(equal).ordinal() < partition.ordinal()){
//If current color is RED (smallest) put it in smallest bucket
Collections.swap(A,smaller++,equal++);
}else if(A.get(equal).ordinal() > partition.ordinal()){
//If current color is BLUE (Largest) put it in largest bucket
Collections.swap(A,larger--,equal++);
}else{
//If current color is white put it in white bucket
equal++;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment