Quick Sort Algorithm

Quick Sort is an efficient algorithm used to order/sort a list of elements in ascending or descending order. It is a type of divide and conquer algorithm: It partitions the list to be sorted into two portions and recursively sorts each portion.

Idea Behind the Algorithm

Let’s say we have a list of numbers L which is unsorted i.e, the numbers in the list are arranged in some random order.

Now suppose we pick one number (n) from the list and then create 2 lists L1 and L2, such that:

• L1 contains all numbers less than the number (n) we picked and
• L2 contains all the numbers greater than or equal the number (n) we picked.

Now we can sort L1 and L2 individually and after both the lists are sorted, we can attach them back into a single sorted list!. This is the idea of quick sort. So in the above example, after sorting both the list, we can combine them into a single list with sequence: L1 + n + L2. Number n we picked for partitioning is termed as the pivot number.

Let’s now look at the routine that partitions a list into two portions by selecting a pivot number and re-arranging other numbers.

Understanding Partitioning Routine

Quick sort algorithm uses a partitioning routine to divide a list into two partitions such that all the numbers in the left partition are less than a number and all the numbers in the right partition are greater than or equal to the same number. This is similar to two pointer algorithm used to sort an array containing only 0s and 1s.

Let’s say we are given the below list and we need to partition the list into two lists such that the above condition holds true.

First we select a random number as the pivot number (number with respect to which all the numbers in left portion have to be less and numbers in the right portion have to be greater than or equal). We move the pivot number (5) to the end of list. Here we selected the center element as the pivot element and moved it to the left.

Now we initialize two pointers: one on left side of the list and one on right side (before pivot element at end) of the list.

We need to advance left pointer towards right until we reach a number greater than or equal the pivot number. We stop at number 9 since this number is greater than the pivot number 5 and so it should go into the right portion of list.

We now need to advance right pointer towards left until we reach a number less than the pivot number. We stop here since this number should go into the left portion of list.

Now we have a number on left side which should go into right portion of list and a number on right side which should go into the left portion of list. So we now swap both the numbers.

We advance the left pointer towards right and right pointer towards left until we reach numbers which are not in the correct partition. We swap both the numbers so that they stay in the correct partition.

In the above state we observe that the partitioning is already done, i.e, all the numbers towards left partition (in blue color) are less than pivot number (5) and all the numbers towards the right partition (in red color) are greater than or equal to the pivot number (5).

We advance the left pointer towards right and the right pointer towards left again. But this time we observe that the right pointer crossed the left pointer and we stop further looking for numbers to swap. So after the right pointer crosses left, we can say that all the numbers are partitioned.

Now we move the pivot number into the place where the left pointer is pointing.

After the above operation, all the numbers to the left of pivot number are less than the pivot number and all the numbers to the right of pivot number are greater than or equal to the pivot number.

You may ask how this partitioning is actually useful in sorting a list. Well, it sorts a list to some degree i.e, in the final sorted list, all the numbers in the left partition stay in the left and all the numbers in the right partition stay in the right. So after partitioning, the left partition and right partition can be sorted independently of each other and it reduces a lot of comparisons.

Quick Sort Algorithm

Quick sort algorithm uses the above partitioning routing to recursively or iteratively partition the input list into two portions and sorts each portion independently using the same partitioning routine. At each partitioning, one number (pivot number) will definitely be placed at the correct position and so the list will be sorted after some finite partitions.

Let’s look at the algorithm steps with visualizations for the input list below:

First we try to partition the input list into two partitions. All numbers in the left partition are less than the pivot number (6 in this case) and all the numbers in the right partition are greater than or equal to the pivot number.

Now that we have partitioned the list, the pivot element is in the correct sorted position and left, right portions can be sorted individually.

We perform partitioning again on the left portion of list and on the right portion of list independently.

After the above step, a total of 4 partitions exist and each of them can be sorted independently.

Partitioning is done again on each of the 4 partitions. Notice that any list with just a single number is already sorted. So we just mark it as sorted without performing partitioning again.

By this step we are left with two lists: One with just a single element and the other with 2 elements.

We mark the single element list as sorted and partition the other list.

Finally, the only available partition contains just a single element. So we mark it as sorted and the entire list is sorted!

All the numbers marked in green are at correct positions, so the entire array is sorted.

In short, the quick sort algorithm can be summarized in the below points:

• Pick a Pivot number and partition the input list into two sub lists
• Recursively sort each sub list
• Combine both the sub lists back into a single sorted list glued with the pivot number

Visualization of Quick Sort Algorithm

Below is the step by step visualization of quick sort algorithm implemented via recursion:

Implementing Quick Sort Algorithm

Top-down Quick Sort (Recursive) Implementation

# Implementation of Quick sort algorithm in Python Language

# function to partition a given list
# and return the partition position 
def partition(array, low, high):

  # choose the center element as pivot
  mid = (low + high) // 2
  pivot = array[mid]
  
  # Move center element to the end
  (array[mid], array[high]) = (array[high], array[mid])

  # initialize right and left pointers
  lp = low
  rp = high-1


  # re arrange elements into correct partition
  # until right and left pointers cross each other
  while lp <= rp:
    
    # Move left pointer until we reach a number
    # greater than or equal to pivot number
    while array[lp] < pivot:
      lp = lp + 1
    
    # Move right pointer until we reach a number
    # less than the pivot number
    while lp <= rp and array[rp] >= pivot:
      rp = rp - 1
    
    if lp < rp:
      (array[lp], array[rp]) = (array[rp], array[lp])

  # Now move the pivot number to partition index
  (array[high], array[lp]) = (array[lp], array[high])
  
  # return the partition index
  return lp

# function to perform quicksort using the partitioning routine
def quickSort(array, low, high):
  if low < high:

    # Partition the list with respect to a pivot such that
    # elements smaller than pivot are on the left
    # elements greater than pivot are on the right
    pi = partition(array, low, high)

    # sort the list on left side of partition
    quickSort(array, low, pi - 1)

    # sort the list on right side of partition
    quickSort(array, pi + 1, high)


data = [68, 70, 28, 94, 67, 48]
print("Unsorted Array")
print(data)

size = len(data)

quickSort(data, 0, size - 1)

print('Sorted Array in Ascending Order:')
print(data)

// Implementation of Quick sort algorithm in C++ Language

#include <bits/stdc++.h>

// function to partition a given list
// and return the partition position 
int partition(std::vector<int> &array, int low, int high){

  // choose the center element as pivot
  int mid = (low + high) / 2;
  int pivot = array[mid];
  
  // Move center element to the end
  std::swap(array[mid], array[high]);

  // initialize right and left pointers
  int lp = low;
  int rp = high-1;


  // re arrange elements into correct partition
  // until right and left pointers cross each other
  while(lp <= rp) {
    
    // Move left pointer until we reach a number
    // greater than or equal to pivot number
    while(array[lp] < pivot){
      lp = lp + 1;
    }
    
    // Move right pointer until we reach a number
    // less than the pivot number
    while(lp <= rp && array[rp] >= pivot){
      rp = rp - 1;
    }
    
    if(lp < rp){
      std::swap(array[lp], array[rp]);
    }
  }
  
  // Now move the pivot number to partition index
  std::swap(array[high], array[lp]);
  
  // return the partition index
  return lp;
}

// function to perform quicksort using the partitioning routine
void quickSort(std::vector<int> &array, int low, int high){
  if(low < high){

    // Partition the list with respect to a pivot such that
    // elements smaller than pivot are on the left
    // elements greater than pivot are on the right
    int pi = partition(array, low, high);

    // sort the list on left side of partition
    quickSort(array, low, pi - 1);

    // sort the list on right side of partition
    quickSort(array, pi + 1, high);
  }
}


// Lets now use quick sort algorithm to sort a list
int main(){
  std::vector<int> data = {68, 70, 28, 94, 67, 48};
  
  std::cout << "Unsorted Array:" << std::endl;
  for(auto n : data) std::cout << n << " ";
  
  quickSort(data, 0, data.size() - 1);
  
  std::cout << std::endl << "Sorted Array in ascending order" << std::endl;
  for(auto n : data) std::cout << n << " ";
  
  return 0;
}

TODO: Bottom-Up Quick Sort (Iterative) Implementation

Characteristics of Quick Sort Algorithm

Time Complexity

Time complexity of quick sort algorithm depends on how ideally the pivot index is selected during each partitioning routine.

• If the pivot point is selected such that it divides the input list exactly into 2, the time complexity will be N log(N) (Partitioning happens over logN layers and each layer requires O(N) time to partition).
• If the pivot point is selected such that no elements exist on one side and all the elements exist on the other side, there will be a total of N layers and so the time complexity is N^2.

In short, the best case time complexity of Quick sort algorithm is O(NlogN) and the worst case time complexity is O(N^2). On an average, assuming that the input list is randomly ordered, the time complexity would be near to O(NlogN).

Space Complexity

Quick sort algorithm can be implemented to sort the list in place. But we require additional stack space while recursively sorting partitioned lists. In best case scenario, the space complexity of quick sort algorithm will be O(logN) an in the worst case, it will be O(N).

Stability

Any sorting algorithm is said to be stable if the relative order of elements with similar id is maintained. For example, if we are given an unordered list of objects [1#, 2%, 1%, 2#], the output has to be [1#, 1%, 2%, 2#]. i.e., the relative order of similar elements has to be maintained.

In this algorithm, during partitioning routine, we do not maintain relative order during swapping. For example, elements with in order 2% and 2# might appear in the final sorted list as 2# and 2%. Hence quick sort is not a stable sorting algorithm.

Resources & References

• pivoting to understand quicksort
• WikiPedia