Skip to content

Instantly share code, notes, and snippets.

@aleksmitov
Created June 14, 2015 21:39
Show Gist options
  • Select an option

  • Save aleksmitov/acf0424640d28286ada7 to your computer and use it in GitHub Desktop.

Select an option

Save aleksmitov/acf0424640d28286ada7 to your computer and use it in GitHub Desktop.
Implementations of the Fisher–Yates shuffle algorithm and Quickselect
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