On 09 Dec 2014, at 09:31, Henrik Johansen <henrik.s.johansen@veloxit.no> wrote:
On 08 Dec 2014, at 7:36 , Sven Van Caekenberghe <sven@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...
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