Skip to content

Instantly share code, notes, and snippets.

@mmurray
Created January 26, 2011 20:33
Show Gist options
  • Save mmurray/797395 to your computer and use it in GitHub Desktop.
Save mmurray/797395 to your computer and use it in GitHub Desktop.
public class Sandbox {
public static Integer[] quicksort(Integer[] array){
if(array.length <= 1){
return array;
}
Integer[] result = new Integer[array.length];
List<Integer> less = new ArrayList<Integer>();
List<Integer> greater = new ArrayList<Integer>();
int pivIndex = 0;
int pivot = array[pivIndex];
for(int i = pivIndex+1; i < array.length; i++){
if(array[i] <= pivot){
less.add(array[i]);
}
if(array[i] > pivot){
greater.add(array[i]);
}
}
result = merge(quicksort(less.toArray(new Integer[0])), pivot, quicksort(greater.toArray(new Integer[0])));
return result;
}
public static Integer[] merge(Integer[] a, int pivot, Integer[] b){
Integer[] result = new Integer[a.length + b.length + 1];
for(int i = 0; i < result.length; i++){
if(i < a.length){
result[i] = a[i];
}else if(i == a.length){
result[i] = pivot;
}else{
result[i] = b[i - (a.length+1)];
}
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
Integer[] array = new Integer[10];
for(int i = 0; i < array.length; i++){
array[i] = (int)(Math.random()*100.0)+1;
}
System.out.println("quicksorting..");
System.out.println();
System.out.println(Arrays.toString(array));
Integer[] result = quicksort(array);
System.out.println(Arrays.toString(result));
}
}
public class Quicksort {
private int[] numbers;
private int number;
public void sort(int[] values) {
// Check for empty or null array
if (values ==null || values.length==0){
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number - 1);
}
private void quicksort(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[low + (high-low)/2];
// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller then the pivot
// element then get the next element from the left list
while (numbers[i] < pivot) {
i++;
}
// If the current value from the right list is larger then the pivot
// element then get the next element from the right list
while (numbers[j] > pivot) {
j--;
}
// If we have found a values in the left list which is larger then
// the pivot element and if we have found a value in the right list
// which is smaller then the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}
private void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment