All about Quick Sort


Quick Sort Video


Strength:

It is QUICK!

Input:

An unordered list of n elements, A.

Remark:

Quick Sort is a recursive function. It will return the origin list when a list of one or zero element is passed to it.


Algorithm:

  1. Pick a pivot, say the last element A[n-1], where n is the length of the list A.
  2. Partition the rest of the elements into two lists, one with all elements less than the pivot, and the other with elements not less than the pivot.
  3. Recursively call quicksort on the left and right partition.
  4. Return the list [left, pivot, right]

Implementation:

  • If input list has one or less element, return the original list.
  • Last element will be the pivot.
  • For each of the rest, compare with pivot.
    • Start with wall=0. 
    • If less than pivot:
      • swop list[wall] and list[i]. Increment wall.
  • Swop list[wall] and list[pivot] (Last element)
  • Recursively call quick sort on list[:wall] and list[wall+1:] and return list[:wall]+list[wall]+list[wall+1:]

Example:



Quick Sort Best Case Scneario



Start: [1, 6, 3, 7, 2, 5, 4]
Left = [1, 3, 2] Pivot = [4], Right = [7, 5, 6]

Start: [1, 3, 2]
Left = [1] Pivot = [2], Right = [3]

Start: [7, 5, 6]
Left = [5] Pivot = [6], Right = [7]