Quick Sort

Quick Sort is a type of sorting algorithm and is based on splitting of an array into subarrays. It is also called partition-exchange sort and divides the array into three partitions namely, elements smaller than the pivot, the pivot, elements larger than the pivot.

The “pivot” element can be any element from the array. To put in simpler terms, we choose any random element and partition the array around it such that the elements to the left of it are smaller and elements to the right of it are larger.

It is a comparison-based in-place sorting algorithm and follows a divide and conquer approach. The efficient implementations of this algorithm are not a stable sort.

Visualization

Video explanation for Quicksort Algorithm.

Pseudo Code
PARTITION(A, p, r)
  x ← A[r]
  i ← p - 1
  for j ← p to r - 1
    do if A[j] ≤ x
      then i ← i + 1
        exchange A[i] ↔ A[j]
  exchange A[i + 1] ↔ A[r]
  return i + 1

RANDOMIZED_PARTITION(A, p, r)
  i ← RANDOM(p, r)
  exchange A[r] ↔ A[i]
  return PARTITION(A, p, r)

QUICKSORT(A, p, r)
  if p < r
    then q ← RANDOMIZED-PARTITION(A, p, r)
    QUICKSORT(A, p, q - 1)
    QUICKSORT(A, q + 1, r)

Implementation in C++


Time Complexity

Worst Case: It occurs when the pivot element picked is always either the greatest or the smallest element.
Time Complexity = O(n2)

Best Case: It occurs when the pivot element is always the middle element or near to the middle element.
Time Complexity = O(nlogn)

Average Case: When it’s neither of the above.
Time Complexity = O(nlogn)

Space Complexity
Extra space required is O(logn) while the Total Space Complexity is O(n).




Written with by Ashwin

Comments