Quicksort, Slowly
Starting with an array:
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}5 \end{array} \]
We first set the values \(low\) and \(high\) that determine the subset of the array in which we'll be working. With this being the first pass, \(low\) will be \(0\) and \(high\) will be \(length - 1\).
We then ask the return condition.
Is \(low \geq high\) ?
No! We've only just started! But this would be \(true\) if the length of the array was \(0\) or \(1\) because an array of length \(0\) or \(1\) is always sorted. We'd then return, breaking the cycle.
We need to find where our first split will be. This will be around the \(pivot\).
We'll set \(pivot\) to \(array[high]\). For now, that's the last item in the array.
We'll also set \(index\) to \(low - 1\).
\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
We'll then loop through the array, from \(low\) to \(high\).
Start!
\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}0}}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}4}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}4}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}4}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
No!
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}4}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}2}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}3}& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}6& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}3}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}6}& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
No!
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}3}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}1}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}1}& \underset{\hphantom{index}}6& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}5} \end{array} \]
Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}5}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
The item at \(pivot\) is now sorted.
The array is now split at \(pivot\).
Items to the left are all less than or equal to \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underline{\underset{\hphantom{index}}0}& \underline{\underset{\hphantom{index}}4}& \underline{\underset{\hphantom{index}}2}& \underline{\underset{\hphantom{index}}3}& \underline{\underset{\hphantom{index}}1}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}5}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Items to the right are all greater than \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}1& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}5}}& \underline{\underset{\hphantom{index}}7}& \underline{\underset{\hphantom{index}}6} \end{array} \]
We'll branch off to the left first.
With \(pivot\ index - 1\) as \(high\), go again!
Is \(low \geq high\) ?
No!
Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).
\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}0& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Start!
\[ \begin{array}{} \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\phantom{0}}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}0}}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}4}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
No!
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
No!
Next Item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}0}& \underset{\hphantom{index}}4& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}1}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
No!
Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
The item at \(pivot\) is now sorted.
The array is now split at \(pivot\).
Items to the left are all less than or equal to \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underline{\underset{\hphantom{index}}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Items to the right are all greater than \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}0& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}1}}& \underline{\underset{\hphantom{index}}2}& \underline{\underset{\hphantom{index}}3}& \underline{\underset{\hphantom{index}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
We'll continue down this path, branching off to the left first.
With \(pivot\ index - 1\) as \(high\), go again!
Is \(low \geq high\) ?
Yes! This item is already sorted!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}4& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
We'll branch off to the right now.
With \(pivot\ index + 1\) as \(low\), go again!
Is \(low \geq high\) ?
No!
Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Start!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}2}}& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Next item!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}3}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}3& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}4}}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
The item at \(pivot\) is now sorted.
The array is now split at \(pivot\).
Items to the left are all less than or equal to \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underline{\underset{\hphantom{index}}2}& \underline{\underset{\hphantom{index}}3}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}4}}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Normally, there would be a second branch where the items to the right are all greater than \(pivot\). Though, in this case, the pivot is the last item in the subset and there are no items to the right! So there is only the branch to the left.
We'll continue down this path.
With \(pivot\ index - 1\) as \(high\), go again!
Is \(low \geq high\) ?
No!
Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Start!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}1}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Is \(item \leq pivot\) ?
Yes! Increase \(index\) by 1 and swap the values of \(index\) and \(item\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\underset{index}{\underset{\substack{\uparrow\\ item}}2}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}2& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}3}}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
The item at \(pivot\) is now sorted.
The array is now split at \(pivot\).
Items to the left are all less than or equal to \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underline{\underset{\hphantom{index}}2}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}3}}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
There is no right branch.
We'll continue down this path.
With \(pivot\ index - 1\) as \(high\), go again!
Is \(low \geq high\) ?
Yes! This item is already sorted!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}6 \end{array} \]
We've finished the original left branch! Let's move on to the right.
With \(pivot\ index - 1\) as \(high\), go again!
Is \(low \geq high\) ?
No!
Set \(pivot\) to \(array[high]\) and \(index\) to \(low - 1\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}5}}& \underset{\hphantom{index}}7& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}6} \end{array} \]
Start!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ index}}{\color{green}5}}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ item}}7}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}6} \end{array} \]
Is \(item \leq pivot\) ?
No!
Finished! Increase \(index\) by 1 and swap \(index\) and \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}6}}& \underset{\hphantom{index}}7 \end{array} \]
The item at \(pivot\) is now sorted.
The array is now split at \(pivot\).
There is no left branch.
Items to the right are all greater than \(pivot\).
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}{\underset{\substack{\uparrow\\ pivot}}{\color{green}6}}& \underline{\underset{\hphantom{index}}7} \end{array} \]
We'll continue down this path.
With \(pivot\ index - 1\) as \(high\), go again!
Is \(low \geq high\) ?
Yes! This item is already sorted!
\[ \begin{array}{} \underset{\hphantom{index}}\ & \underset{\hphantom{index}}{\color{green}0}& \underset{\hphantom{index}}{\color{green}1}& \underset{\hphantom{index}}{\color{green}2}& \underset{\hphantom{index}}{\color{green}3}& \underset{\hphantom{index}}{\color{green}4}& \underset{\hphantom{index}}{\color{green}5}& \underset{\hphantom{index}}{\color{green}6}& \underset{\hphantom{index}}{\color{green}7} \end{array} \]
All Finished!
We can visualize the result as a tree:
Write it in Python!
# quicksort.py
import time
from typing import List
def quicksort(array: List[int]) -> List[int]:
def _quicksort(array: List[int], low: int, high: int):
if low >= high:
return
pivot_index = _partition(array, low, high)
_quicksort(array, low, pivot_index-1)
_quicksort(array, pivot_index+1, high)
def _partition(array: List[int], low: int, high: int) -> int:
pivot = array[high]
index = low - 1
for item in range(low, high):
if array[item] <= pivot:
index += 1
temp = array[item]
array[item] = array[index]
array[index] = temp
index += 1
array[high] = array[index]
array[index] = pivot
return index
_quicksort(array, 0, len(array)-1)
return array
array = [0, 4, 7, 2, 3, 6, 1, 5]
start_time = time.time()
sorted_array = quicksort(array[:])
print(f'{array} → {sorted_array} in {(time.time() - start_time) * 1000:.3f}ms') $ python quicksort.py
[0, 4, 7, 2, 3, 6, 1, 5] → [0, 1, 2, 3, 4, 5, 6, 7] in 0.008ms 0.008ms?! Maybe we'll let the computer handle it from now on...