Quick Sort

1. Quick Sort Algorithm
2. Quick Sort Example
3. Quick Sort Algorithm Implementation
4. Quick Sort Algorithm Complexity

Quick sort is a highly efficient sorting algorithm based on the principle of the divide and conquer algorithm. Quick sort works by partitioning the array into two parts around a selected pivot element. It moves smaller elements to the left side of the pivot and larger elements to the right side. After this, left and right subparts are recursively sorted to sort the whole array. It is called Quick sort because it is around 2 or 3 times quicker than common sorting algorithms. Quick sort is widely used for information search and numerical computations inside data structures.

Quick Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements. Take two variables, beg & end, then store the index of starting and ending element.

Partition()

QuickSort()

Quick Sort Example

Suppose we have the array: (6,5,1,4,2,3). We will sort it using the quick sort algorithm.

Quick Sort Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Quick Sort Algorithm Complexity

Time Complexity

• Average Case

Time taken by Quick Sort is given by the following recurrence relation:

 T(n) = T(k) + T(n-k-1) + θ(n)

k here represents the number of elements smaller/larger than the pivot element.

This result of this recurrence relation gives T(n) = nLogn.The average-case occurs when we get random unevenly balanced partitions. The time complexity is of the order of [Big Theta]: O(nLogn).

• Worst Case

T(n) = T(n-1) + θ(n)

The worst-case occurs when the pivot element is always either the largest or smallest element of the array. In this case, all the elements fall in one subarray and maximum n calls have to be made. The worst-case time complexity is [Big O]: O(n²).

• Best Case

 T(n) = 2T(n/2) + θ(n)

The best-case occurs when the selected pivot element is always the middle element or when both the partitions are evenly balanced i.e. difference in size is 1 or less. The best-case time complexity is [Big Omega]: O(nLogn).

Space Complexity

The average-case space complexity for the quick sort algorithm is O(Logn). It is the space required by the recursion stack. But in the worst-case when sorting an array requires n recursive, the space complexity is O(n).