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

Comments

[William Torrez]

Why use algorithm? When use algorithm?

[Gustavo]

An algorithm is supposed to make operations like sorting or search better, there are good and bad solutions, but most of the time it depends on your goal.

For example, when you need to search an array that is not sorted, you might use linear seach, but, if that array is sorted, you could you binary search and make it a loooooot more efficient

[William Torrez]

Can i use two algorithm at the same time?

[Gustavo]

Yes, you can, but if you should or shouldn't do depends on what's your goal.

Let me see if I get your question with these two examples:

• You have an app that displays an array of movies, you initially use the quicksort for sorting the array, and then you want to search for a specific item, you can use the binary search algorithm.
• You want to build an image recognition system that needs to identify objects in real-time, such as cars, pedestrians, and traffic signs. In order to achieve accurate object recognition, you can decide to use two different algorithms: one that is good at identifying shapes and one that is good at identifying colors.