Quick Sort

Quick sort is a divide-and-conquer sorting algorithm that divides the input array into two sub-arrays, recursively sorts each sub-array, and then combines the sorted sub-arrays. The algorithm is not stable and has a time complexity of $O(N\log N)$ on average and $O(N^2)$ in the worst case.

Features

• Stable sorting algorithm
• In-place sorting algorithm

Implementation

The implementation of quick sort depends on the choice of pivot element. The following is an implementation of quick sort using the median-of-three pivot selection strategy.

Pseudocode

procedure quickSort(A : list of sortable items)
    quickSort(A, 0, length(A) - 1)
end procedure

procedure quickSort(A : list of sortable items, low : integer, high : integer)
    if low < high then
        pivot = partition(A, low, high)
        quickSort(A, low, pivot - 1)
        quickSort(A, pivot + 1, high)
    end if
end procedure

procedure partition(A : list of sortable items, low : integer, high : integer) : integer
    pivot = medianOfThree(A, low, high)
    swap(A[pivot], A[high])
    i = low
    for j = low to high - 1 do
        if A[j] <= A[high] then
            swap(A[i], A[j])
            i = i + 1
        end if
    end for
    swap(A[i], A[high])
    return i
end procedure

procedure medianOfThree(A : list of sortable items, low : integer, high : integer) : integer
    mid = low + (high - low) / 2
    if A[low] > A[mid] then
        swap(A[low], A[mid])
    end if
    if A[low] > A[high] then
        swap(A[low], A[high])
    end if
    if A[mid] > A[high] then
        swap(A[mid], A[high])
    end if
    return mid
end procedure

Java

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

private static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = medianOfThree(arr, low, high);
    swap(arr, pivot, high);
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] <= arr[high]) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, high);
    return i;
}

private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) {
        swap(arr, low, mid);
    }
    if (arr[low] > arr[high]) {
        swap(arr, low, high);
    }
    if (arr[mid] > arr[high]) {
        swap(arr, mid, high);
    }
    return mid;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Runtime Analysis

Given $N$ elements in the array, the time complexity of quick sort is $O(N\log N)$ on average and $O(N^2)$ in the worst case.

Best Case

The best case occurs when the pivot element divides the array into two equal sub-arrays. In this case, the algorithm makes $\log N$ recursive calls, each of which takes $O(N)$ time to partition the array. The time complexity is $\Omega (N\log N)$.

Worst Case

The worst case occurs when the pivot element is the smallest or largest element in the array. In this case, the algorithm makes $N$ recursive calls, each of which takes $O(N)$ time to partition the array. The time complexity is $O(N^2)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.