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
...