Created
June 14, 2015 21:39
-
-
Save aleksmitov/acf0424640d28286ada7 to your computer and use it in GitHub Desktop.
Implementations of the Fisher–Yates shuffle algorithm and Quickselect
This file contains hidden or 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.Random; | |
| public class Test { | |
| /* | |
| * Implementation of the Fisher–Yates shuffle algorithm with O(N) time complexity | |
| */ | |
| public static <T> void shuffle(ArrayList<T> items) | |
| { | |
| if(items == null) throw new NullPointerException(); | |
| Random numberGenerator = new Random(); | |
| for(int i = items.size()-1; i > 0; --i) | |
| { | |
| numberGenerator.setSeed(System.nanoTime()); | |
| int randomIndex = numberGenerator.nextInt(i+1); | |
| T temp = items.get(i); | |
| items.set(i, items.get(randomIndex)); | |
| items.set(randomIndex, temp); | |
| } | |
| } | |
| public static <T extends Comparable<T>> T orderStatistic(ArrayList<T> items, int index) | |
| { | |
| if(items == null) throw new NullPointerException(); | |
| if(index < 1 || index > items.size()) throw new IllegalArgumentException(); | |
| shuffle(items); | |
| return orderStatistic(items, index-1, 0, items.size()-1); | |
| } | |
| /* | |
| * Implementation of Quickselect with O(N) average time complexity | |
| */ | |
| private static <T extends Comparable<T>> T orderStatistic(ArrayList<T> items, int index, int start, int end) | |
| { | |
| //SELECTING PIVOT | |
| int pivotElementIndex = end; | |
| //PIVOT SELECTED | |
| //SWAPPING WITH LAST ELEMENT | |
| T temp = items.get(pivotElementIndex); | |
| items.set(pivotElementIndex, items.get(end)); | |
| items.set(end, temp); | |
| //SWAPPED | |
| //PARTITIONING THE ARRAY | |
| int counter = start; | |
| int i; | |
| for(i = start; i < end && counter < end; ++i) | |
| { | |
| int itemIndexLessThanPivot = -1; | |
| while(counter < end) | |
| { | |
| if(items.get(counter).compareTo(items.get(end)) <= 0) | |
| { | |
| itemIndexLessThanPivot = counter; | |
| ++counter; | |
| break; | |
| } | |
| ++counter; | |
| } | |
| if(itemIndexLessThanPivot == -1) break; //there is no such element | |
| //SWAP THE ELEMETS | |
| temp = items.get(i); | |
| items.set(i, items.get(itemIndexLessThanPivot)); | |
| items.set(itemIndexLessThanPivot, temp); | |
| //ELEMENTS SWAPPED | |
| } | |
| //PUTTING THE PIVOT IN PLACE | |
| temp = items.get(i); | |
| items.set(i, items.get(end)); | |
| items.set(end, temp); | |
| //PIVOT PUT IN PLACE | |
| //ARRAY PARTITIONED | |
| if(i == index) return items.get(i); | |
| else if(i < index) return orderStatistic(items, index, i+1, end); | |
| else return orderStatistic(items, index, start, i-1); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment