Created
August 13, 2017 23:40
-
-
Save sdpatil/6eefa17bc6d00d0c364feabeebfc6da3 to your computer and use it in GitHub Desktop.
Dutch National Flag Problem/Can reach end
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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