IMG_2988.jpeg

# Lecture 11: October 26, 2023 ## Quick sort - Invented by Tony Hoare in 1959 - $O(n \log n)$ expected time - $O(n^2)$ worst-case time - Sorts *in place* Here is pseudocode for quicksort: ``` Partition(A, p, r) 1 x = A[r] 2 i = p - 1 3 for j = p to r - 1 4 if A[j] x$ 3. `A[j.. r - 1]` values...

# Lecture 11: October 26, 2023 ## Quick sort - Invented by Tony Hoare in 1959 - $O(n \log n)$ expected time - $O(n^2)$ worst-case time - Sorts *in place* Here is pseudocode for quicksort: ``` Partition(A, p, r) 1 x = A[r] 2 i = p - 1 3 for j = p to r - 1 4 if A[j] x$ 3. `A[j.. r - 1]` values not yet considered 4. `A[r]` $= x$ ### Example execution: Original array: | 5 | 3 | 2 | 6 | 4 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | p | | | | | | | r | $i = p - 1$ $x = A[r] = 7$ First iteration: | 5 | 3 | 2 | 6 | 4 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | p | | | | | | j | r | | i = p | | | | | | | | $A[j] \le x$, so increment $i$, and exchange $A[i]$ with $A[j]$ (but they're the same). Second iteration: | 5 | 3 | 2 | 6 | 4 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | p | | | | | j | r | | | i = p + 1 | | | | | | | $A[j] \le x$, so increment $i$, and exchange $A[i]$ with $A[j]$ (but they're the same). Third iteration: | 5 | 3 | 2 | 6 | 4 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | p | | | | j | r | | | | i = p + 2 | | | | | | $A[j] \le x$, so increment $i$, and exchange $A[i]$ with $A[j]$ (but they're the same). Fourth iteration: | 5 | 3 | 2 | 6 | 4 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | p | | | j | r | | | | | i = p + 2 | | | | | Now $A[j] > x$, so we do nothing. Fifth iteration: | 5 | 3 | 2 | 6 | 4 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | p | | j | r | | | | | | i = p + 2 | | | | Now $A[j] \le x$, so increment $i$ ($i = p + 3$), and exchange $A[i]$ with $A[j]$ | 5 | 3 | 2 | 4 | 6 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | p | | j | r | | | | | i = p + 3 | | | | Sixth iteration: | 5 | 3 | 2 | 4 | 6 | 1 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | p | j | r | | | | | | | i = p + 3 | | | Now $A[j] \le x$, so increment $i$ ($i = p + 4$), and exchange $A[i]$ with $A[j]$ | 5 | 3 | 2 | 4 | 1 | 6 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | p | j | r | | | | | | | i = p + 4 | | | Seventh iteration: | 5 | 3 | 2 | 4 | 1 | 6 | 3 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | p | r | | | | | | | | i = p + 4 | | Now $A[j] \le x$, so increment $i$ ($i = p + 5$), and exchange $A[i]$ with $A[j]$ | 5 | 3 | 2 | 4 | 1 | 3 | 6 | 7 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | | p | r | | | | | | | | i = p + 5 | | Now we exchange $A[i + 1]$ with $A[r]$ | 5 | 3 | 2 | 4 | 1 | 3 | 7 | 6 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | | i + 1 | r | Done!