Last active
February 21, 2016 03:06
-
-
Save metajungle/62bddff55708bf7a3da7 to your computer and use it in GitHub Desktop.
Quick sort in Java using the left-most element as the pivot
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
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