Quick sort algorithm in C++

In this post I'll show what I learned from the quicksort algorithm. I'll be sorting in ascending order an int array in C++.

The pivot

The quicksort algorithm is based on the pivot you choose. It can be the first, last, the middle or you can have other ways of choosing the pivot, like median-of-three.

Where the pivot is supposed to be

You should be asking where are we putting this pivot. Well, the pivot should abide by some rules so we know it is in its right place:

• It occupies the right sorted position on the given array.
• All items to the left are smaller
• All items to the right are bigger

The partition function

In this example, I'll be choosing the last element as the pivot.
In the function we call partition, we are going to find the right index where the pivot is supposed to be and return it to use in our quicksort function.

#include <iostream>

using namespace std;

const int ARR_SIZE = 7;

int partition(int arr[], int left, int right)
{
  int pivot = arr[right]; // get the last element as pivot
  int sortedIndex = left - 1;

  for (int j = left; j < right; j++)
  {
    if (arr[j] < pivot)
    {
      sortedIndex++;
      swap(arr[sortedIndex], arr[j]);
    }
  }

  swap(arr[sortedIndex + 1], arr[right]);
  return sortedIndex + 1;
}

• sortedIndex will store the previous index that the pivot will occupy at the end of the function
• We iterate from left to right.
• If the element is smaller than the pivot, we add + 1 to sortedIndex and swap the elements arr[sortedIndex] and arr[j]
• At the end of the function, we swap the pivot (last element) with the sortedIndex + 1th element, and we return the new index of the pivot.

The Quick Sort recursive function

• In the quicksort function, we receive the array, the left and the right index.

• Here we are basically getting the correct pivot position with the partition function and dividing the array in two:

  • from left to pivot - 1
  • from pivot + 1 to right

• The stop criteria is when the function receives left equal or bigger than right.

• And like that, we have our quicksort function:
  
  

void quicksort(int arr[], int left, int right)
{
  if (left < right)
  {
    int pivot = partition(arr, left, right);

    quicksort(arr, left, pivot - 1);
    quicksort(arr, pivot + 1, right);
  }
}

Final code

Let's use an array with 7 positions and sort it using the quicksort function:

#include <iostream>

using namespace std;

const int ARR_SIZE = 7;

int partition(int arr[], int left, int right)
{
  int pivot = arr[right];
  int sortedIndex = left - 1;

  for (int j = left; j < right; j++)
  {
    if (arr[j] < pivot)
    {
      sortedIndex++;
      swap(arr[sortedIndex], arr[j]);
    }
  }

  swap(arr[sortedIndex + 1], arr[right]);
  return sortedIndex + 1;
}

void quicksort(int arr[], int left, int right)
{
  if (left < right)
  {
    int pivot = partition(arr, left, right);

    quicksort(arr, left, pivot - 1);
    quicksort(arr, pivot + 1, right);
  }
}

int main()
{
  int arr[ARR_SIZE] = {3, 7, 8, 4, 6, 2, 5};

  cout << "\n-------------Original array-------------\n";
  for (int i = 0; i < ARR_SIZE; i++)
  {
    cout << arr[i] << " ";
  }

  quicksort(arr, 0, ARR_SIZE - 1);

  cout << "\n-------------Sorted array-------------\n";
  for (int i = 0; i < ARR_SIZE; i++)
  {
    cout << arr[i] << " ";
  }

  return EXIT_SUCCESS;
}

Hope you could find it useful! If you have any advice, tips, recommendations or doubts, just ping me on Twitter