Created
December 3, 2011 23:47
-
-
Save noahlz/1428536 to your computer and use it in GitHub Desktop.
Java implementation of in-place Quick Sort. See http://en.wikipedia.org/wiki/Quick_sort#In-place_version
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.Arrays; | |
import java.util.Random; | |
/** | |
* See http://en.wikipedia.org/wiki/Quick_sort#In-place_version | |
*/ | |
public class QuickSort { | |
private static final Random random = new Random(); | |
private static final int RANDOM_INT_RANGE = 100; | |
public static void main(String[] args) { | |
int[] arr = newTestArray(25); | |
int[] copy = Arrays.copyOf(arr, arr.length); | |
System.out.println("Starting array: " + Arrays.toString(arr)); | |
sort(arr); | |
// check the result | |
Arrays.sort(copy); | |
if(Arrays.equals(arr, copy)) { | |
System.out.println("Sorted array: " + Arrays.toString(arr)); | |
} else { | |
System.err.println("ERROR: expected " + Arrays.toString(copy) + " but was " + Arrays.toString(arr)); | |
} | |
} | |
private static int[] newTestArray(int size) { | |
final int[] arr = new int[size]; | |
for (int i = 0; i < arr.length; i++) { | |
arr[i] = random.nextInt(RANDOM_INT_RANGE); | |
} | |
return arr; | |
} | |
private static void sort(int[] arr) { | |
if(arr.length > 0) | |
sortInPlace(arr, 0, arr.length - 1); | |
} | |
private static void sortInPlace(int[] arr, int left, int right) { | |
if(left >= right) return; // sorted | |
final int range = right - left + 1; | |
int pivot = random.nextInt(range) + left; | |
int newPivot = partition(arr, left, right, pivot); | |
sortInPlace(arr, left, newPivot - 1); | |
sortInPlace(arr, newPivot + 1, right); | |
} | |
private static int partition(int[] arr, int left, int right, int pivot) { | |
// we're going to move around the values in the array. | |
// > than this pivot value goes to the right, | |
// < than this pivot value goes to the left | |
int pivotVal = arr[pivot]; | |
// temporarily move the pivot value out of the way... | |
swapArrayVals(arr, pivot, right); | |
int storeIndex = left; | |
for(int i = left; i <= (right - 1); i++) { | |
if(arr[i] < pivotVal) { | |
swapArrayVals(arr, i, storeIndex); | |
storeIndex++; | |
} | |
} | |
swapArrayVals(arr, storeIndex, right); | |
System.out.println("Array sorted so far: " + Arrays.toString(arr)); | |
return storeIndex; | |
} | |
private static void swapArrayVals(int[] arr, int from, int to) { | |
int fromVal = arr[from]; | |
int toVal = arr[to]; | |
arr[from] = toVal; | |
arr[to] = fromVal; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment