Stable sort?

[Hal Fulton]

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.sortname).sortage).sortheight)

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]

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.sortname).sortage).sortheight)

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]

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

Yes, I see what you mean.

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]

Yes, I see what you mean.



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/

Hal

E

 

[Hal Fulton]

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]

Hi,

In message "Re: Stable sort?"

|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]

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]

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]

unsubscribe

---------------------
[Alexander P. Javier]
[[email protected]]
[[email protected]]
[[email protected]]
[[email protected]]
---------------------
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]
---------------------

-----Original Message-----
From: gabriele renzi [mailto:[email protected]]
Sent: Thursday, March 17, 2005 02.10 pm
To: ruby-talk ML
Subject: Re: Stable sort?

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.

 

[Mathieu Bouchard]

2. Further I believe that such an algorithm could be used to implement
multi-key sorts as "chained" sorts -- correct?
people.sortname).sortage).sortheight)

no, maybe this:

a=people.sortname)
a.each_extentname) {|i,n|
a[i,n].sort!age)
a[i,n] = a[i,n].each_extentage) {|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.__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.sortname)
a.each_extentname) {|i,n|
b=people.part(i,n)
b.sort!age)
b.each_extentage) {|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]

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)