Skip to content

Instantly share code, notes, and snippets.

@artlovan
Last active April 17, 2017 21:15
Show Gist options
  • Save artlovan/ed6732493caae384bdce3edce7bfa056 to your computer and use it in GitHub Desktop.
Save artlovan/ed6732493caae384bdce3edce7bfa056 to your computer and use it in GitHub Desktop.
QuickSort in Java
import java.util.Arrays;
public class QuickSort {
private static int[] data = new int[]{19, 43, 35, 20, 50, 47, 42, 43, 47, 47};
public static void main(String[] args) {
System.out.println(Arrays.toString(data));
sort();
System.out.println(Arrays.toString(data));
}
public static void sort() {
sort(0, data.length - 1);
}
private static void sort(int left, int right) {
if (right - left > 0) {
int pivot = data[right];
int pivotLocation = partition(left, right, pivot);
sort(left, pivotLocation - 1);
sort(pivotLocation + 1, right);
}
}
private static int partition(int left, int right, int pivot) {
int leftPartition = left - 1;
int rightPartition = right;
while (true) {
while (data[++leftPartition] < pivot);
while (data[--rightPartition] > pivot && rightPartition > 0);
if (leftPartition >= rightPartition) {
break;
}
swap(leftPartition, rightPartition);
}
swap(leftPartition, right);
return leftPartition;
}
private static void swap(int i1, int i2) {
int temp = data[i1];
data[i1] = data[i2];
data[i2] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment