Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Stable sort?

526 views
Skip to first unread message

Hal Fulton

unread,
Mar 16, 2005, 10:09:19 PM3/16/05
to
Questions for you guys...

Correct my terminology and/or my perceptions if they
are mistaken.

1. I think the term "stable sort" is used for a sorting
algorithm that preserves the relative order of records
that have the same key -- correct?

2. Further I believe that such an algorithm could be used
to implement multi-key sorts as "chained" sorts -- correct?
people.sort(:name).sort(:age).sort(:height)

3. Further I believe that Ruby's standard sort is not
stable. (Isn't it a quicksort-like thing?)


Given that, what is a good stable sort algorithm? Would
it be too inefficient to implement in Ruby or no?


Thanks,
Hal

Patrick Hurley

unread,
Mar 16, 2005, 10:21:24 PM3/16/05
to
> 1. I think the term "stable sort" is used for a sorting
> algorithm that preserves the relative order of records
> that have the same key -- correct?

Yup

> 2. Further I believe that such an algorithm could be used
> to implement multi-key sorts as "chained" sorts -- correct?
> people.sort(:name).sort(:age).sort(:height)

Sure, but I am guessing you would want to reverse the order of the sorting.

> 3. Further I believe that Ruby's standard sort is not
> stable. (Isn't it a quicksort-like thing?)

Not sure, but quicksorts are not stable

> Given that, what is a good stable sort algorithm? Would
> it be too inefficient to implement in Ruby or no?

Mergesort is a good choice. Efficency should be reasonable depending
upon data set sizes. Therea re of course other possiblities. When in
doubt:

D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and
Searching. Addison-Wesley, Reading MA, 1973.


Hal Fulton

unread,
Mar 16, 2005, 10:42:11 PM3/16/05
to
Patrick Hurley wrote:
>
>>2. Further I believe that such an algorithm could be used
>>to implement multi-key sorts as "chained" sorts -- correct?
>> people.sort(:name).sort(:age).sort(:height)
>
> Sure, but I am guessing you would want to reverse the order of the sorting.

Yes, I see what you mean.

>>Given that, what is a good stable sort algorithm? Would
>>it be too inefficient to implement in Ruby or no?
>
> Mergesort is a good choice. Efficency should be reasonable depending
> upon data set sizes. Therea re of course other possiblities. When in
> doubt:
>
> D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and
> Searching. Addison-Wesley, Reading MA, 1973.

Yes... I always had one handy, but now I don't. I should actually
buy one.

Anyone ever implemented mergesort in Ruby? Got one handy?


Hal


ES

unread,
Mar 16, 2005, 11:13:24 PM3/16/05
to

Looks like the invaluable Bruno R Preiss has quite a few algorithms
in his back pocket: http://www.brpreiss.com/books/opus8/programs/

> Hal

E

Hal Fulton

unread,
Mar 16, 2005, 11:19:16 PM3/16/05
to
ES wrote:
>>> Mergesort is a good choice. Efficency should be reasonable depending
>>> upon data set sizes. Therea re of course other possiblities. When in
>>> doubt:
>>>
>>> D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and
>>> Searching. Addison-Wesley, Reading MA, 1973.
>>
>>
>>
>> Yes... I always had one handy, but now I don't. I should actually
>> buy one.
>>
>> Anyone ever implemented mergesort in Ruby? Got one handy?
>
>
> Looks like the invaluable Bruno R Preiss has quite a few algorithms
> in his back pocket: http://www.brpreiss.com/books/opus8/programs/

I was just looking at that... but I don't yet get it.

Does "merge" imply two lists? I'm just looking at a single list.


Hal

Yukihiro Matsumoto

unread,
Mar 16, 2005, 11:20:09 PM3/16/05
to
Hi,

In message "Re: Stable sort?"


on Thu, 17 Mar 2005 12:09:19 +0900, Hal Fulton <hal...@hypermetrics.com> writes:

|1. I think the term "stable sort" is used for a sorting
|algorithm that preserves the relative order of records
|that have the same key -- correct?

I think. so.

|3. Further I believe that Ruby's standard sort is not
|stable. (Isn't it a quicksort-like thing?)

It's using quick sort algorithm, which is not stable.

|Given that, what is a good stable sort algorithm? Would
|it be too inefficient to implement in Ruby or no?

The simplest way is to use sort_by,

n = 0
ary.sort_by {|x| n+= 1; [x, n]}

which is inefficient, but not too much I guess.

matz.


Martin DeMello

unread,
Mar 17, 2005, 12:12:26 AM3/17/05
to
Hal Fulton <hal...@hypermetrics.com> wrote:
>
> Does "merge" imply two lists? I'm just looking at a single list.

It's a recursive algorithm:

def sort(ary, from, to)
mid = (from + to)/2
merge(
sort(ary, from, mid),
sort(ary, mid+1, to))
end

'merge' interleaves two already-sorted sublists.

martin



gabriele renzi

unread,
Mar 17, 2005, 1:07:14 AM3/17/05
to
Hal Fulton ha scritto:

> Given that, what is a good stable sort algorithm? Would
> it be too inefficient to implement in Ruby or no?

AFAIK, python's sort is based on a alghoritm named something like
"stable natural mergesort" wich is said to be quite impressive, but I
know nothing about it. I guess implementing it in pure ruby would have
bad performance, anyway.

Alexander P. Javier

unread,
Mar 17, 2005, 1:33:40 AM3/17/05
to
unsubscribe

---------------------
[Alexander P. Javier]
[al...@foo.ncc.gov.ph]
[alx...@gmail.com]
[aly...@hotmail.com]
[al...@yahoo.com]
---------------------
Message checked by:
- Avast! Professional 4.6 [4.6.623/0511-0]
- Sygate Personal Firewall Pro 5.5.271 [4.0.2/1.0.1058]
---------------------

Mathieu Bouchard

unread,
Mar 21, 2005, 6:40:15 AM3/21/05
to

On Thu, 17 Mar 2005, Hal Fulton wrote:

> 2. Further I believe that such an algorithm could be used to implement
> multi-key sorts as "chained" sorts -- correct?
> people.sort(:name).sort(:age).sort(:height)

no, maybe this:

a=people.sort(:name)
a.each_extent(:name) {|i,n|
a[i,n].sort!(:age)
a[i,n] = a[i,n].each_extent(:age) {|i_,n_|
# gets worse here...
}
}

where #each_extent is like each_index but also gives the number of
elements with the same key and then skip over them:

class Array
def each_extent(sym)
i=j=0
while j<length
i=j
j+=1 while self[i].__send__(sym)==self[j].__send__(sym)
yield i,j-i
end
end
end

Then you could use SubArray (found in MetaRuby) to sort everything
in-place, but MetaRuby's sort is slow, because it's written in Ruby *and*
because speed never was a concern there. Then it would be:

a=people.sort(:name)
a.each_extent(:name) {|i,n|
b=people.part(i,n)
b.sort!(:age)
b.each_extent(:age) {|i_,n_|
# etc
}
}

Then Matz suggested using sort_by with an array. If that is too heavy,
then you can use any order-preserving function (that is, for which
f(x)<f(y) exactly when x<y), as long as it returns something simpler than
an array. However, that pretty much just means Fixnum, and not Array, and
it's not really feasible to stay in the Fixnum range while keeping those
condensed-keys easy to compute...

_____________________________________________________________________
Mathieu Bouchard -=- Montréal QC Canada -=- http://artengine.ca/matju


jm

unread,
Mar 24, 2005, 1:24:23 AM3/24/05
to

On 21/03/2005, at 10:40 PM, Mathieu Bouchard wrote:

>
> On Thu, 17 Mar 2005, Hal Fulton wrote:
>
>> 2. Further I believe that such an algorithm could be used to implement
>> multi-key sorts as "chained" sorts -- correct?
>> people.sort(:name).sort(:age).sort(:height)
>

here's another one for no other reason than I need to write one. Has
the advantage that you can elect which value to hold stable. May not be
as efficient as the others (haven't benchmarked), but a good excuse to
work out how to use inject and a bit of a bull at the gate
implementation.

J.

Struct.new('Simp',:name,:second,:value)
initial = [
Struct::Simp.new('b',2,'value4'),
Struct::Simp.new('c',2,'value7'),
Struct::Simp.new('b',3,'value5'),
Struct::Simp.new('c',1,'value6'),
Struct::Simp.new('c',3,'value8'),
Struct::Simp.new('a',1,'value1'),
Struct::Simp.new('a',2,'value2'),
Struct::Simp.new('b',1,'value3'),
]
a = initial
a.sort!{|x,y| x[:name] <=> y[:name]}

# group by field f1, and sub sort on f2
def subsort (ary,f1,f2)
tmp = [[],[]]
out = ary.inject(tmp) {|t,s|
if t[1].empty? or t[1][0][f1] == s[f1]
t[1] << s
else
t[1].sort! {|x,y| x[f2] <=> y[f2]}
t[0] << t[1]
# t[0].flatten! # not really needed
t[1] = []
t[1] << s
end
t
}
out[1].sort! {|x,y| x[f2] <=> y[f2]}
out.flatten!
end

puts '=== initial ==='
puts initial
puts '=== result ==='
puts subsort(initial,:name,:second)


0 new messages