OpenEuphoria

stable sorting

• Posted by Juergen Luethje <eu.lue at gmx.de> Feb 25, 2003
• 511 views

I wrote:

> Subject: Re: Euphoria 2.4 Alpha-test Release!

[...]
> 5) Documentation of sort():
>    Nothing special with version 2.4, I just came across it.
>    I think it would be valuable to mention, whether or not the sorting
>    of sort() is stable, along with a short explanation for beginners,
>    what that means.
[...]

Probably I should have been somewhat more specific. I actually was
thinking more of custom_sort(), than of sort():
Say I have a list of records with student names and marks, already
sorted by name. Then i want to sort this list by mark, so that students
with the same mark remain listed in alphabetical order.

The following code (modified after 'csort.ex') does *not* perform a
stable sorting.

----------=----------=----------=----------=----- begin of code
include sort.e

constant MARK = 2
constant statistics = {
   {"Doe", 3},
   {"Einstein", 1},
   {"Goldberg", 1},
   {"Irving", 4},
   {"Jones", 3},
   {"Miller", 2},
   {"Neuman", 2},
   {"Petersen", 4},
   {"Smith", 2},
   {"Zander", 5}
}

function compare_mark (sequence a, sequence b)
   -- Compare two sequences (records) according to MARK.
   return compare(a[MARK], b[MARK])
end function

integer by_mark
sequence sorted_by_mark

by_mark  = routine_id("compare_mark")
sorted_by_mark = custom_sort(by_mark, statistics)

puts(1, "sorted by mark\n\n")
for i = 1 to length(sorted_by_mark) do
   printf(1, "%12s %d\n", sorted_by_mark[i])
end for
----------=----------=----------=----------=----- end of code

Is there a library in the archive, with which this can be achieved?
I didn't find one.

Ricardo, I saw that your functions GradeDown() and GradeUp() in
'genfunc.e' perform stable sorting. But given the above example, there
is no way to tell them just to sort by mark, and not to compare the
whole records, right?


Best regards,
   Juergen

-- 
 /"\  ASCII ribbon campain  |
 \ /  against HTML in       |  Superstition brings bad luck.
  X   e-mail and news,      |
 / \  and unneeded MIME     |