# Algorithms: Quicksort (General Algorithm)

## Quicksort (General Algorithm)

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: