Quick Sort/Pseudocode

Quick Sort Algorithm Notes

Nice notes here from Skiena: https://charlesreid1.com/wiki/Quick_Sort#Notes

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)