## Wednesday, September 17, 2014

### Quick Sort Implementation [Java]

Quicksort makes O(n log n) comparisions to sort n items. In the worst case, it makes O(n^2) comparisions. Quicksort is often faster in practice than other O(n log n) algorithms. Qucicksort is a comparison sort.

Quicksort is NOT a stable sort.
Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during recursion.

This video has a really nice explanation of the algorithm:

Code:

```import java.util.Arrays;

public class QuickSort {

public static void quickSort(int array[]) {
quickSorter(array, 0, array.length - 1);
}

public static void quickSorter(int array[], int lo, int hi) {
if (lo > hi) return;

int partition = partition(array, lo, hi);
quickSorter(array, lo, partition - 1);
quickSorter(array, partition + 1, hi);
}

private static int partition(int array[], int lo, int hi) {
int partitionIndex = lo;

for (int i = lo; i <= hi; ++i) {
if (array[i] < array[hi]) {
int temp = array[partitionIndex];
array[partitionIndex] = array[i];
array[i] = temp;
partitionIndex++;
}
}
int temp = array[partitionIndex];
array[partitionIndex] = array[hi];
array[hi] = temp;
return partitionIndex;
}

public static void main(String[] args) {
int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
quickSort(array);
System.out.println(Arrays.toString(array));
}
}```

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]