In this algorithms video, we explain the quicksort algorithm for sorting an array of elements. (Note that the algorithm that we give here is a simpler version that works only for distinct elements. We will give the full version later.) The algorithm is called "quick" because it is generally considered to be the fastest sorting algorithm. It is difficult to say for certain whether quicksort is always the fastest sorting algorithm, and one of the chief difficulties of the algorithm consists in selecting a proper pivot.

The selection of a pivot element is the first action that is performed in what we call the partition step. The partition step is a process that divides an unsorted array of elements into two smaller arrays and the pivot element. The elements to the left of the pivot are all smaller than the pivot and the elements to the right of the pivot are all larger than the pivot, as shown below. Of course, if there are multiple elements that that are equal to the pivot they may end up on either side.

Above, we show the result of the partition step; the pivot, 34, is shown in white. To get the partition, we must first select a pivot. We would like the pivot to be the median or middle value of the array. However, finding this is a time-consuming process. So, we settle for a less expensive method of selecting a pivot. In our example code below, we just select the pivot at random from the array.

Once the pivot is selected, we select successive elements from the beginning of the array that are greater than or equal to the pivot and select elements from the end of the array that are less than or equal to the pivot. Once we find one of each of these, we swap their values and move the selectors toward the opposite ends of the array and repeat until the selectors meet at the pivot. This partitions the array.

To perform the quicksort algorithm, we partition the array once. Then we apply the partition algorithm recursively on each partition of the array. We continue doing this until the partition size is either 0 or 1. When no partition is larger than 1 element, the array is sorted. The C++ code for the quicksort algorithm is given below. In order to make the code more easily understandable, it has not been optimized.

#include <iostream>
#include <ctime>

void Partition(int* ipA, int iSize) {

    // Partitions of size 0 or 1 are already sorted
    if (iSize <= 1) {
        return;
    }

    // Select a pivot from the array randomly
    int iPivot = ipA[rand() % iSize];

    // Indices of the entries to be swapped
    int iLower = 0;
    int iUpper = iSize - 1;

    // Partition array into sections above and below the pivot
    while (iLower < iUpper) {

        while (ipA[iLower] < iPivot) {
            ++iLower;
        }

        while (ipA[iUpper] > iPivot) {
            --iUpper;
        }

        // Swap the entries at the lower and upper indices
        int iTemp       = ipA[iLower];
        ipA[iLower]     = ipA[iUpper];
        ipA[iUpper]     = iTemp;
    }

    // Recursively call partition on each partititon.
    Partition(ipA, iLower);
    Partition(&(ipA[iLower + 1]), iSize - iLower - 1);
}

void Quicksort(int* ipA, int iSize) {
    // Seed the random number generator
    srand((unsigned int)time(0));
    Partition(ipA, iSize);
}

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19, 43, 2};
    int iSize = 9;

    Quicksort(iaArray, iSize);

    // Output sorted array
    for (int i = 0; i < iSize; i++){
        cout << iaArray[i] << "  ";
    }
    cout << endl;

    return 0;
}