How does the quicksort algorithm work?

The QuickSort algorithm is a recursive algorithm that works on the principle of "divide and conquer".

1. Choosing a pivot element: One element is selected from the array. There are several methods for choosing it: the first element, the last, the median of three, or a random element.
2. Partitioning: The array elements are rearranged so that all elements less than the pivot come before it, and all greater elements come after it. Elements equal to the pivot can be in either part. After this partitioning, the pivot element is in its final sorted position.
3. Recursive sorting of subarrays: The algorithm is recursively applied to the subarray of elements less than the pivot and to the subarray of elements greater than the pivot.

The base case of recursion is an array of one or zero elements, which is already considered sorted.

Pseudocode:

quicksort(arr, low, high)
  if low < high
    pivot_index = partition(arr, low, high)
    quicksort(arr, low, pivot_index - 1)
    quicksort(arr, pivot_index + 1, high)

Partition function (example):

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choose the last element as pivot
    int i = (low - 1); // Index of the last element less than the pivot

    for (int j = low; j <= high - 1; j++) {
        // If the current element is less than or equal to the pivot
        if (arr[j] <= pivot) {
            i++; // Increment the index of the last element less than the pivot
            std::swap(arr[i], arr[j]); // Swap the current element with the element at index i
        }
    }
    std::swap(arr[i + 1], arr[high]); // Place the pivot in its correct position
    return (i + 1); // Return the index of the pivot
}

Complexity:

• Average: Space complexity O(log n) (due to recursive calls), time complexity O(n log n).
• Worst case: Space complexity O(n) (with unbalanced partitioning), time complexity O(n^2) (when the smallest or largest element is always chosen as the pivot). This can be avoided with a good pivot selection method.