On 08 Dec 2014, at 19:59, Alexandre Bergel <alexandre.bergel@me.com> wrote:

Well written and very dictactic.

Thanks, that was the idea.

Do you have this text as a class comment in your class?

Well, not completely, but there are links to the article in the class comment: https://github.com/svenvc/lampsort/tree/master/LampSort.package/LampSort.cla...

Cheers, Alexandre

...

Le 08-12-2014 à 15:36, Sven Van Caekenberghe <sven@stfx.eu> a écrit :

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

On 08 Dec 2014, at 20:28, Tudor Girba <tudor@tudorgirba.com> wrote:

Very nice :)

Thanks!

I really like these pieces of work. A couple more and you'll have a book ready :).

A virtual book, then ;-)

Doru

On Mon, Dec 8, 2014 at 8:17 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:

...

On 08 Dec 2014, at 19:59, Alexandre Bergel <alexandre.bergel@me.com> wrote:

Well written and very dictactic.

Thanks, that was the idea.

...

Do you have this text as a class comment in your class?

Well, not completely, but there are links to the article in the class comment:

https://github.com/svenvc/lampsort/tree/master/LampSort.package/LampSort.cla...

...

Cheers, Alexandre

...

Le 08-12-2014 à 15:36, Sven Van Caekenberghe <sven@stfx.eu> a écrit :

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

-- www.tudorgirba.com

"Every thing has its own flow"

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

Because the array sorts in place, and it seems good practice to copy literal constants (it does not matter much in a workspace, but it does lead to problems in actual code where the constants are stored in methods). I could have added the sort: / sorted: distinction but I went for as little methods as possible.

On 10 Dec 2014, at 03:05, stepharo <stepharo@free.fr> wrote:

Sven

why do you copy the array passed to sort?

Stef Le 8/12/14 10:36, Sven Van Caekenberghe a écrit :

...

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