Implement Quicksort Editorial

Practice Problem Link: Implement Quicksort | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array, sort it using quicksort.

Approach

Quicksort is a divide and conquer algorithm. 

• The basic idea is to divide the array into two parts about an element(say pivot point) such that the pivoted element is at the same position as the sorted array and all elements before the pivot point are less than the pivoted element and all elements after the pivot point are greater than or equal to the pivoted element.
• Both the parts will be called recursively and the above process will be repeated. In this way, the array will break further until each partition becomes sorted.

Note: Here, the last element of the partition is used as the pivoted element.

Analysis

• Time Complexity:
  • Best Case: O(n * log(n))
  • Average Case: O(n * log(n))
  • Worst Case: O(n²)
• Auxiliary Space Complexity: O(log(n))

Implementation

C++

int makePartition (vector<int> &arr, int low, int high) {
   int pivot = arr[high];
   int currentIndx = low - 1;
   for (int i = low; i < high; i++) {
       if (arr[i] < pivot) {
           currentIndx++;
           int temp = arr[i];
           arr[i] = arr[currentIndx];
           arr[currentIndx] = temp;
       }
   }
   int temp = arr[high];
   arr[high] = arr[currentIndx + 1];
   arr[currentIndx + 1] = temp;
   return currentIndx + 1;
}
void quicksort (vector<int> &arr, int low, int high) {
   if (low < high) {
       int pivot = makePartition (arr, low, high);
       quicksort (arr, low, pivot - 1);
       quicksort (arr, pivot + 1, high);
   }
}
void quickSort(vector<int> &arr) {
   int n = arr.size();
   quicksort (arr, 0, n-1);
}

Java

class Solution {
   int makePartition (int[] arr, int low, int high) {
       int pivot = arr[high];
       int currentIndx = low - 1;
       for (int i = low; i < high; i++) {
           if (arr[i] < pivot) {
               currentIndx++;
               int temp = arr[i];
               arr[i] = arr[currentIndx];
               arr[currentIndx] = temp;
           }
       }
       int temp = arr[high];
       arr[high] = arr[currentIndx + 1];
       arr[currentIndx + 1] = temp;
       return currentIndx + 1;
   }
   void quicksort (int[] arr, int low, int high) {
       if (low < high) {
           int pivot = makePartition (arr, low, high);
           quicksort (arr, low, pivot - 1);
           quicksort (arr, pivot + 1, high);
       }
   }
   void quickSort (int[] arr) {
       int n = arr.length;
       quicksort (arr, 0, n-1);
   }
}