Quick sort algorithm in C++
Tags: cpp, algorithms, quicksort
Published: 2023-03-07 13:52:37

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](https://ece.uwaterloo.ca/~dwharder/aads/Algorithms/Sorting/Quick_sort/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.

```cpp
#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 + 1`th 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:
```cpp
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:

```cpp
#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