Search⌘ K
AI Features
Home
Courses
Competitive Programming - Crack Your Coding Interview, C++

Quick Sort - Implementation

Discover how to implement Quick Sort with recursive partitioning. Learn to manage pivot elements, swap mechanisms, and recursive calls to efficiently sort arrays. Understand various time complexities of Quick Sort in different scenarios.

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.

C++
#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
...