On Fri, 25 Apr 2003, Fredrik (Naranek) Hubinette (Real Build Master) @ Pike (-) developers forum wrote:
If I remember correctly, sort does not allocate any memory if you sort an array with only one reference.
That was the reason for my question. But quicksort doesn't take extra memory (at least in theory). On the other hand it is not stable, that votes pro quicksort beeing the current algorithm.
Either way, I would be more conserned with how much extra time it takes than how much extra memory it takes.
agreed. Yet there should exist a fast, stable, in situ algorithm suited as a general purpose sorting algorithm for pike. If that is not the case, it could be interesting to provide a second algorithm e.g. _sort that would be optimized for almost sorted arrays and stable.
--- Ludger
/HubbeOn Wed, 23 Apr 2003, Martin Stjernholm, Roxen IS @ Pike developers forum wrote:
It's very simple: Just remember the original position and sort on that when items are equal otherwise. That requires a little bit more memory so a separate stable version could be considered. But I don't think it's worth the trouble since sort() already temporarily allocates memory linear to the size of the sorted array.
which algorithm are you actually using?
--- Ludger
/ Martin Stjernholm, Roxen IS
Previous text:
2003-04-23 16:18: Subject: sort
Martin Stjernholm had somewhat interesting ideas regarding making any unstable sort algorithm stable with a more or less cheap wrapper. I'm hoping he might comment on the subject. :)
/ Johan Sundström (folkskådare)
/ Fredrik (Naranek) Hubinette (Real Build Master)
Previous text:
2003-04-24 09:30: Subject: Re: sort
On Wed, 23 Apr 2003, Martin Stjernholm, Roxen IS @ Pike developers forum wrote:
It's very simple: Just remember the original position and sort on that when items are equal otherwise. That requires a little bit more memory so a separate stable version could be considered. But I don't think it's worth the trouble since sort() already temporarily allocates memory linear to the size of the sorted array.
which algorithm are you actually using?
--- Ludger
/ Martin Stjernholm, Roxen IS
Previous text:
2003-04-23 16:18: Subject: sort
Martin Stjernholm had somewhat interesting ideas regarding making any unstable sort algorithm stable with a more or less cheap wrapper. I'm hoping he might comment on the subject. :)
/ Johan Sundström (folkskådare)
/ Brevbäraren