Skip to content

Instantly share code, notes, and snippets.

@metajungle
Last active February 21, 2016 03:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save metajungle/62bddff55708bf7a3da7 to your computer and use it in GitHub Desktop.
Save metajungle/62bddff55708bf7a3da7 to your computer and use it in GitHub Desktop.
Quick sort in Java using the left-most element as the pivot
package net.metajungle.sorting;
import java.util.Arrays;
public class QuickSort {
/**
* Quick sort the given array in ascending order
*
* @param array
*/
public void sort(int[] array) {
sort(array, 0, array.length - 1);
}
/**
* Quick sort the given array starting from index
* {@code l} to {@code r}
*
* Uses the first element in the array as the pivot
*
* @param array
* @param l
* @param r
*/
private void sort(int[] array, int l, int r) {
if (l < r) {
// select pivot element (left-most)
int pivot = array[l];
// partition and shuffle around pivot
int i = l;
int j = r;
while (i < j) {
// move right to avoid pivot element
i += 1;
// scan right: find elements greater than pivot
while (i <= r && array[i] < pivot) {
i += 1;
}
// scan left: find elements smaller than pivot
while (j >= l && array[j] > pivot) {
j -= 1;
}
if (i <= r && i < j) {
// swap around pivot
swap(array, i, j);
}
}
// put pivot in correct place
swap(array, l, j);
// sort partitions
sort(array, l, j - 1);
sort(array, j + 1, r);
}
}
/**
* Swap elements at indexes {@code i} and {@code j}
* in the give array
*
* @param array
* @param i
* @param j
*/
private void swap(int[] array, int i, int j) {
if (i >= 0 && j >= 0 && i < array.length && j < array.length) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
/**
* Main method
*
* @param args
*/
public static void main(String[] args) {
int[] array = new int[] {
14, 5, 1, 2, 15, 6, 16, 4, 9, 8, 7
};
new QuickSort().sort(array);
System.out.println("Sorted: " + Arrays.toString(array));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment