Quick Sort - Implementation

Use Recursion to implement Quick Sort.

We'll cover the following...

Implementation

In the Quick Sort lesson, we discussed the logic to implement the Quick Sort. So without wasting any time, let’s jump right into the code.

Press + to interact
#include <iostream>
using namespace std;
int partition(int *arr, int left, int right, int pivot)
{
int leftPointer = left;
int rightPointer = right;
while(true) {
while(arr[leftPointer] < pivot) {
leftPointer++;
}
while(rightPointer > 0 && arr[rightPointer] > pivot) {
rightPointer--;
}
if(leftPointer >= rightPointer)
break;
else
{
int temp = arr[leftPointer];
arr[leftPointer] = arr[rightPointer];
arr[rightPointer] = temp;
}
}
int temp = arr[leftPointer];
arr[leftPointer] = arr[rightPointer];
arr[rightPointer] = temp;
return leftPointer;
}
void quickSort(int *arr, int left, int right)
{
if(right-left <= 0)
return;
else {
int pivot = arr[right];
int partitionPoint = partition(arr, left, right, pivot);
quickSort(arr, left, partitionPoint-1);
quickSort(arr, partitionPoint+1, right);
}
}
int main() {
int arr[7] = {4,6,3,2,1,9,7};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
}

Explanation:

  • On line 4, we define our partition() function, which will move the pivot element to its correct position.
  • On line 9, we run a loop with an infinite condition.
  • On lines 10 and 11, we run an inner loop, which will make the value of leftPointer as the index till which all the elements are smaller than pivot. As soon as the element becomes greater than pivot, we come out of the loop and leftPointer points to the index of that greater element (which needs to be swapped).
  • On lines 14 and 15, we run
...