Quick sort partition algorithm is sometimes taught differently. :) So, thought of covering that too. There is no difference in performance or space usage. Only advantage is, this method is little bit straight forward.
Instead of taking the pivot and incrementing 2 counts: i and j both starting from the left, we can maintain left & right with left starting from the start and right starting from the end.
As we know that, left needs to have lesser items and right needs to have greater items. until we have appropriate items, we can simply skip it. This is little bit clearer since the skip we do is not so clear in old partition approach.
After we skip perfectly “ok” left and right, what we have will be swappable items. We continue this until we meet the condition left > right.
After we do all the swaps and ready with left & right lists smaller & greater. We can simply swap the element in the location where right is.
- I felt this approach, little bit confusing.. :) If you are not used to lots of counters.. be with the old approach
- The above code taken from: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html
- Even though a[low] is the pivot, we include that as well in the comparison. This is also another difference in this algorithm.