All about Quick Sort
It is QUICK!
An unordered list of n elements, A.
Quick Sort is a recursive function. It will return the origin list when a list of one or zero element is passed to it.
- Pick a pivot, say the last element A[n-1], where n is the length of the list A.
- 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.
- Recursively call quicksort on the left and right partition.
- Return the list [left, pivot, right]
- 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:]
Start: [1, 6, 3, 7, 2, 5, 4]
Left = [1, 3, 2] Pivot = , Right = [7, 5, 6]
Start: [1, 3, 2]
Left =  Pivot = , Right = 
Start: [7, 5, 6]
Left =  Pivot = , Right =