> On 09 Dec 2014, at 09:31, Henrik Johansen <henrik.s.johan...@veloxit.no> > wrote: > > >> On 08 Dec 2014, at 7:36 , Sven Van Caekenberghe <s...@stfx.eu> wrote: >> >> Hi, >> >> Here is another article I just published >> >> LampSort, a non-recursive QuickSort implementation >> >> The divide and conquer partitioning is at the heart of QuickSort >> >> >> https://medium.com/@svenvc/lampsort-a-non-recursive-quicksort-implementation-4d4891b217bd >> >> Pharo makes it easy to implement this non-recursive version of QuickSort - >> and beautiful as well. >> >> Sven >> >> > Nice! > A minor nitpick: > partition: interval > | pivot index | > pivot := data at: interval first. > data swap: interval first with: interval last. > index := interval first. > Doesn't it make more sense to pick the last element as pivot if you're going > to iterate from the start anyways? > Saves you a swap per partition :)
Maybe, we should try, but it saves only one single swap. The goal of the example is not to build the most optimised implementation though. This particular partitioning code allows for a general 'pick any pivot' strategy. The concrete choice of pivot is a separate, interesting subject with various pros and cons: http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot Thanks for the feedback. > Cheers, > Henry
