Sort A Vector Of Integers With The Quicksort Algorithm In C++

If you’re studying computer science, at some point you’re going to be exposed to the Quicksort algorithm. Even if you’re not a computer science student, chances are this particular algorithm will come up at some point in time as part of an interview. I’ve been asked about it plenty of times in interview processes and never once used it again.

Whether or not you’ll ever use the Quicksort algorithm, it is important to know and that is what we’re going to review in this back to the basics tutorial.

In this tutorial we’re going to sort a vector of integer values using the Quicksort algorithm. We’re going to use a vector because it is a commonly used data structure in C++.

A long time ago I actually wrote about using Quicksort with Java. While the language is different, we’re going to take advantage of the same strategy.

The idea behind the Quicksort algorithm is, given an array or similar data structure, you’re going to split it into two smaller arrays based on a pivot point or index within that array, ideally at the center of the array. The items at each side of the array are compared against the pivot value and swapped.

Let’s take a look at the following code to produce our vector of integer values:

vector<int> values;
for(int i = 0; i < 10; i++) {
    values.push_back(rand() % 200);
}

The above code will create a vector with ten values where each value is a random number between zero and two hundred. So let’s think about partitioning our vector and swapping the values. We could create a function like the following:

int partition(vector<int> &values, int left, int right) {
    int pivotIndex = left + (right - left) / 2;
    int pivotValue = values[pivotIndex];
    int i = left, j = right;
    int temp;
    while(i <= j) {
        while(values[i] < pivotValue) {
            i++;
        }
        while(values[j] > pivotValue) {
            j--;
        }
        if(i <= j) {
            temp = values[i];
            values[i] = values[j];
            values[j] = temp;
            i++;
            j--;
        }
    }
    return i;
}

In the function declaration itself, we are passing the vector of values, but we are passing a reference to that vector. We’re doing this so we can modify the original vector directly in the function without having to return anything.

Inside the function we are using simple math to calculate the center point for the pivot based on the lower and outer bounds of the vector. Remember we’re going to be cutting our vector into smaller sections so the lower and outer bounds might not necessarily be zero and the total size of the vector.

With a while loop we are looping while the lower bounds is less than or equal to the upper. While this condition is true we can do two more loops. The first will increase our lower bounds for as long as the value at that index is less than the value of the pivot. Likewise we’re going to decrease the upper bounds index for as long as the value is greater than the pivot value.

When the loops are done, we’ve found values to be swapped. The swapping of values continues until both bounds values intersect.

The i value will act as our new bounds variable for the next iteration of our sort.

With the partitioning of the data under control, let’s take a look at the rest of the Quicksort. Take a look at the following quicksort function:

void quicksort(vector<int> &values, int left, int right) {
    if(left < right) {
        int pivotIndex = partition(values, left, right);
        quicksort(values, left, pivotIndex - 1);
        quicksort(values, pivotIndex, right);
    }
}

To better understand the above function, let’s assume we actually try to use it. Remember when we declared our vector and added ten random values to it? Let’s expand upon that:

vector<int> values;
for(int i = 0; i < 10; i++) {
    values.push_back(rand() % 200);
}

quicksort(values, 0, values.size() - 1);

for(vector<int>::iterator it = values.begin(); it != values.end(); it++) {
    cout << *it << endl;
}

So how does it relate to the quicksort function? Well, we have our vector of values and we are specifying our lower and upper bounds. The lower bounds is the beginning of the vector at index zero and the upper bounds is the size of the vector minus one because our index starts at zero, not one.

When we start the quicksort function, left will be less than right, so we’ll call the partition function which will cut the vector down the middle, do some swapping, and return a new pivot index to use. Then we can split our vector again and recursively call our quicksort algorithm. This will continue to break down our vector into smaller parts and do swapping until it is sorted.

When the vector can no longer be partitioned or it is fully sorted, the quicksort functions will just terminate.

Conclusion

We just saw how to do the Quicksort algorithm in C++ using vectors instead of arrays. One key difference between using vectors and arrays is the use of the reference of &values rather than values. By including the & we are able to modify the vector in place rather than work with copies of it. Because of how C++ handles arrays with functions, it isn’t necessary when working with standard arrays.

From an algorithm perspective, if you’re looking for the time complexity of the Quicksort algorithm, in a best case scenario it will be O(nlogn) and in a worst case scenario it will be O(n^2).

If you need more help when it comes to vectors and arrays in C++, check out my previous tutorial on the topic titled, Getting Familiar with Arrays and Vectors in C++.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.