In this algorithms lesson video, we explained the general quicksort algorithm for sorting an array of ordered elements. The quicksort algorithm makes repeated use of a partition step, which separates the array into two sections. These two sections contain elements that are less than or equal to the pivot and elements that are greater than or equal to the pivot, where the pivot is a randomly selected element of the array. We have explained the algorithm in the video. Here, we will explain how the algorithm is implemented in the C++ program below.

main()

We will explain this C++ code in the order of execution. Inside the main() function, we declare and initialize an array of ten integers. Afterward, we use a size calculation to initialize the value for iSize so that the array size can be changed at any time without affecting the code. Then we fill the array with randomly generated integer values from 0 to 9. Next, we output the unsorted array. After that, we perform the quicksort algorithm by calling the Quicksort() function. Finally, we output the sorted array.

Quicksort()

The Quicksort() function takes a pointer to an array of integers and the size of the array. Inside the Quicksort() function, we seed the random number generator by calling the srand() function. Then we call the Partition() function to begin the recursion.

Partition()

Like the Quicksort() function, the Partition() function takes an array and its size. Inside, we first check that the array size is larger than 1; this is the stopping condition since an array of size 1 is, by definition, sorted. Next, we select the pivot randomly from all but the first element of the array.

Note that we avoid choosing the first element because it causes problems when it is the smallest and is chosen as the pivot. In that case, the partition split generates a partition of size zero. This is not a fatal problem because the random selection process will eventually choose a different pivot, but it can slow things down a little.

Once we have selected the pivot, we initialize the lower and upper selectors. Then we enter the main while loop that performs the partition. Inside this loop, are two do-while loops: one to move the lower selector up and one to move the upper selector down. Once the lower selector reaches an element that is greater than or equal to the pivot and the upper selector reaches an element that is less than or equal to the pivot, they stop and the entries are swapped if the lower selector is below the upper selector. Notice that using do-while loops means that newly swapped entries will be skipped over in each new loop. This is also why we initialized the selectors to be outside the array bounds.

The main while loop continues swapping elements. Once it is done, the lower index sits at the start of the second partition. This index is used to sets the bounds for the recursive calls. The new lower partition ends just before the lower index, while new upper partition starts at the lower index. We make the recursive function calls to Partition() accordingly.

#include <iostream>
#include <ctime>

void Partition(int* ipA, int iSize) {

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

    // Select the pivot randomly, but not the first element
    int iPivot = ipA[(rand() % (iSize - 1)) + 1];

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

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

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

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

        // Swap the entries at the lower and upper indices
        if (iLower < iUpper) {
            int iTemp       = ipA[iLower];
            ipA[iLower]     = ipA[iUpper];
            ipA[iUpper]     = iTemp;
        }
    }

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

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[] = {1,2,3,4,5,6,7,8,9,10};
    int iSize = sizeof(iaArray)/sizeof(int);

    // Randomly fill the array with integers (0-9)
    srand((unsigned int)time(0));
    for (int i = 0; i < iSize; i++) {
        iaArray[i] = rand() % 10;
    }

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

    Quicksort(iaArray, iSize);

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

    return 0;
}

This code can be added to a simple console project, like the one from C++ Console Lesson 1. Pressing (Ctrl + F5) compiles and executes the code. An example output is shown below for illustration. Since the arrays are generated randomly, your output will look similar but not exactly like this: