Quicksort.md (682B)
1 +++ 2 title = 'Quicksort' 3 +++ 4 # Quicksort 5 Divide and conquer. 6 7 Algorithm: 8 1. Make right-most index value pivot 9 2. partition array using pivot value 10 3. quicksort left partition recursively 11 4. quicksort right partition recursively 12 13 Find the pivot value: 14 1. Choose highest index value as pivot 15 2. Two variables point left and right of list (except pivot) 16 3. Left points to low index 17 4. Right points to high index 18 5. While value at left < pivot; move right 19 6. While value at right > pivot; move left 20 7. If *both* step 5 and step 6 fail — swap 21 8. If left ≥ right, point where they met is new pivot 22 23 Time complexity: 24 25 - Best case: O(nlogn) 26 - Worst case: O(n^2) 27 - Average case: O(nlogn)