HGPA

Quick Sort

tl;dr Review

 >             <
 L     P       R
[5,8,7,2,1,4,6,3]
 ^       ^
 L<----->R
[1,8,7,2,5,4,6,3]
   ^   ^
   L<->R
[1,2,7,8,5,4,6,3]
     ^
    L&R

Quicksort:

  1. Pivot
    • select a pivot index
  2. Partition:
    • swap values such that:
      • values < pivot are on left side of pivot
      • values > pivot are on right side of pivot
      • pivot is in final sorted location
  3. Recurse:
    • Quicksort each of the two partitions

Partition (Hoare):

  1. while value < pivot move left pointer forward
  2. while value > pivot move right pointer backward
  3. now that you've found values on each side that actually belongs in the other:
    • swap them
    • move both pointers inwards
  4. repeat

Performance:

Note: If you pick pivot to be first or last element, you will always be swapping it

Overview

Quicksort is a divide & conquer sorting algorithm. Primary work is in divide phase: partition.

Implementation

Parameters for both quicksort and partition:

Some implementations pass the pivot in as parameter.

Some implementations will refer to left and right as "lo and hi". This works well for 3-way partitioning, e.g. lo, mid, hi.

McDowell (2008)

The following implementation is a Python rework of McDowell, 2015. It is a two-way quicksort that always chooses the middle of the array as the pivot.

def quicksort(array, left, right):
  index = partition(array, left, right)
  if left < index - 1:
    quicksort(array, left, index - 1)
  if index < right:
    quicksort(array, index, right)

def partition(array, left, right):
  pivot = array[(left + right) / 2]
  while left <= right:
    while array[left] < pivot:
      left += 1
    while array[right] > pivot:
      right -= 1
    if left <= right:
      a[left], a[right] = a[right], a[left]
      left += 1
      right -= 1
  return left

REFERENCES

Sorting and Searching. Cracking the Coding Interview. Sixth Edition. Gayle Laakmann McDowell. 2015.

4.5 Mergesort: Sorting by Divide-and-Conquer. The Algorithm Design Manual. Steven S. Skiena. 2008.

Filename: quick-sort.md (Edit)
Modified: 2017-03-02 (4a31da1724b9099576185b76637f3c6dbc599bd6)
Created: 2017-02-13 (90146112ed92793904489f308bee2a61c40864f0)