From charlesreid1

Quick Sort Algorithm Notes

Nice notes here from Skiena:

Quick sort, like merge sort, requires addressing some topics in the respective language:

  • implement an array or list-like data structure
  • implement a generic type data structure (start simple with integers and strings if it is up to us)
  • implement custom comparator for custom objects
  • random choice of pivot
  • heap (tree) data structure
  • recursion (and recursion limits)

Split the quicksort operation into two parts:

  • the main quicksort function (recursive)
  • the partition function (rearrange the elements of the array around the pivot, and return the index of the pivot - along with the "pivoted" data)

Recursive Quick Sort

function quicksort( array[] s, int low_index, int high_index ):
    // Allocate var for index of partition
    p = 0
    if (hi-lo)>0:
        p = partition( s, lo, hi )
        quicksort(s, lo, p-1)
        quicksort(s, p+1, hi)

Quick Sort with Heap