Quicksort is a divide and conquer algorithm which relies on a partition
operation: to partition an array, we choose an element, called a pivot, move
all smaller elements before the pivot, and move all greater elements after
it. This can be done efficiently in linear time and in-place. We then
recursively sort the lesser and greater sublists. Efficient implementations
of quicksort (with in-place partitioning) are typically unstable sorts and
somewhat complex, but are among the fastest sorting algorithms in practice.
Together with its modest O(log n) space usage, this makes quicksort one of
the most popular sorting algorithms, available in many standard libraries.
The most complex issue in quicksort is choosing a good pivot element;
consistently poor choices of pivots can result in drastically slower (O(n²))
performance, but if at each step we choose the median as the pivot then it
works in O(n log n).
package com.sort.quick;
import java.util.Arrays;
public class QuickSort {
public void sort(int[] data) {
quickSort(data, 0, data.length - 1);
}
private void quickSort(int[] data, int start, int end) {
if (start < end) {
int middle = partition(data, start, end);
quickSort(data, start, middle - 1);
quickSort(data, middle + 1, end);
}
}
public int partition(int[] data, int bottom, int top) {
int pivot = data[top];
int firstAfterSmall = bottom;
for (int i = bottom; i < top; i++) {
if (data[i] < pivot) {
swap(data, firstAfterSmall, i);
firstAfterSmall++;
}
}
swap(data, firstAfterSmall, top);
return firstAfterSmall;
}
private void swap(int[] data, int pivot, int i) {
int temp = data[i];
data[i] = data[pivot];
data[pivot] = temp;
}
public static void main(String[] args) {
int[] data = new int[] { 23,16,8,15,42,4 };
new QuickSort().sort(data);
System.out.println(Arrays.toString(data));
}
}
