Smalltalk › Pharo › Pharo Smalltalk Users

[ Article ] LampSort, a non-recursive QuickSort implementation

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

9 messages Options

Sven Van Caekenberghe-2

[ Article ] LampSort, a non-recursive QuickSort implementation

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

abergel

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

Well written and very dictactic.
Do you have this text as a class comment in your class?

Cheers,
Alexandre

> Le 08-12-2014 à 15:36, Sven Van Caekenberghe <[hidden email]> 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-4d4891b217bd
>
> Pharo makes it easy to implement this non-recursive version of QuickSort - and beautiful as well.
>
> Sven
>
>

Sven Van Caekenberghe-2

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

> On 08 Dec 2014, at 19:59, Alexandre Bergel <[hidden email]> 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.class

> Cheers,
> Alexandre
>
>
>> Le 08-12-2014 à 15:36, Sven Van Caekenberghe <[hidden email]> 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-4d4891b217bd
>>
>> Pharo makes it easy to implement this non-recursive version of QuickSort - and beautiful as well.
>>
>> Sven
>>
>>
>

Tudor Girba-2

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

Very nice :)

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

Doru

On Mon, Dec 8, 2014 at 8:17 PM, Sven Van Caekenberghe <[hidden email]> wrote:

> On 08 Dec 2014, at 19:59, Alexandre Bergel <[hidden email]> 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.class

> Cheers,
> Alexandre
>
>
>> Le 08-12-2014 à 15:36, Sven Van Caekenberghe <[hidden email]> 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-4d4891b217bd
>>
>> 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"

Henrik Sperre Johansen

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

In reply to this post by Sven Van Caekenberghe-2

On 08 Dec 2014, at 7:36 , Sven Van Caekenberghe <[hidden email]> 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 :)

Cheers,

Henry

Sven Van Caekenberghe-2

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

> On 09 Dec 2014, at 09:31, Henrik Johansen <[hidden email]> wrote:
>
>
>> On 08 Dec 2014, at 7:36 , Sven Van Caekenberghe <[hidden email]> 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

Sven Van Caekenberghe-2

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

In reply to this post by Tudor Girba-2

> On 08 Dec 2014, at 20:28, Tudor Girba <[hidden email]> 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 <[hidden email]> wrote:
>
> > On 08 Dec 2014, at 19:59, Alexandre Bergel <[hidden email]> 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.class
>
> > Cheers,
> > Alexandre
> >
> >
> >> Le 08-12-2014 à 15:36, Sven Van Caekenberghe <[hidden email]> 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-4d4891b217bd
> >>
> >> 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"

stepharo

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

In reply to this post by Sven Van Caekenberghe-2

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-4d4891b217bd
>
> Pharo makes it easy to implement this non-recursive version of QuickSort - and beautiful as well.
>
> Sven
>
>
>

Sven Van Caekenberghe-2

Re: [ Article ] LampSort, a non-recursive QuickSort implementation

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 <[hidden email]> 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-4d4891b217bd
>>
>> Pharo makes it easy to implement this non-recursive version of QuickSort - and beautiful as well.
>>
>> Sven
>>
>>
>>
>
>