quick sort is a divide and conquer algorithm, much like quad_trees.
You essentially find a place where one element should be, then sort the left and right side of that element.
TODO add taocp algorithm here 1. Choose an array element e := the partitioning
element. Rearrange so that a[1], …, a[i − 1]
are less than or equal to e,
a[i] = e,
and a[i + 1], …, a[n]
are greater than or equal to e
2. Sort elements indexed at 1, …, i − 1 recursively using quick
sort. 3. Sort elements indexed at i + 1, …, n recursively
using quick sort.
The method in which we rearrange step 1. is important for efficiency, but for our sake, let’s use something simple.
TODO possible make your own version of quicksort in case you cannot sell this commercially. See http://knking.com/books/c2/programs/qsort.c
quick sort is too complex for arrays with elements less than 25.