Quick Sort

Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation is defined. On average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is at one end of the spectrum of divide-and-conquer algorithms, which does most of the work during the partitioning and the recursive calls.

Steps

1. Choose any element of the array to be the pivot.
2. Divide all other elements (except the pivot) into two partitions which is all elements less than the pivot must be in the first partition and all elements greater than the pivot must be in the second partition.
3. Use recursion to sort both partitions.
4. Join the first sorted partition, the pivot, and the second sorted partition.

The best pivot creates partitions of equal length (or lengths differing by 1). The worst pivot creates an empty partition, for example if the pivot is the first or last element of a sorted array. The runtime of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.

Below are the pseudocode on how quick sort works

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

import java.util.*; import java.lang.*; public class QuickSort { public static void main(String[] args) { int[] x = { 99, 22, 14, 37, 13, 87, 100 }; System.out.println(Arrays.toString(x)); int low = 0; int high = x.length - 1; quickSort(x, low, high); System.out.println(Arrays.toString(x)); } public static void quickSort(int[] arr, int low, int high) { if (arr == null || arr.length == 0) return; if (low >= high) return; // pick the pivot int middle = low + (high - low) / 2; int pivot = arr[middle]; // make left < pivot and right > pivot int i = low, j = high; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j--; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // recursively sort two sub parts if (low < j) quickSort(arr, low, j); if (high > i) quickSort(arr, i, high); } }