Have you come across a STABLE sort? A Stable sort is one in which all the incoming elements which evaluate to an equal value when tested for sorting purposes remain in the same order in the output as they were in the input. Perhaps I had better give you an example.

I have a log file and there's a date in every line, but the lines are NOT in date order. And I want to sort my lines so that every line for each day is grouped together, by ascending date order. However, within any particular day I want my output records to remain in the same order that they were in in the input file.

Input data:
20070903 John Smith etc
20070901 Bill Jones
20070902 Arthur Clark
20070903 George Hill
20070902 Arthur Dent
20070903 Petal Honour-Flower

Stable sort output required:
20070901 Bill Jones
20070902 Arthur Clark
20070902 Arthur Dent
20070903 John Smith etc
20070903 George Hill
20070903 Petal Honour-Flower

As compared to output from a standard (default) sort:
20070901 Bill Jones
20070902 Arthur Clark
20070902 Arthur Dent
20070903 George Hill
20070903 John Smith etc
20070903 Petal Honour-Flower

Sorting in Tcl

Here is the sample code to demonstrate those various sorts in Tcl:

proc first {this that} {
set one [lindex $this 0]
set two [lindex $that 0]
return [string compare $one $two]
}
 
lappend mystuff {20070903 John Smith etc}
lappend mystuff {20070901 Bill Jones}
lappend mystuff {20070902 Arthur Clark}
lappend mystuff {20070903 George Hill}
lappend mystuff {20070902 Arthur Dent}
lappend mystuff {20070903 Petal Honour-Flower}
 
puts "Report in initial order"
puts [join $mystuff \n]
puts "-------------------------"
 
puts "Sorts by Forename within date"
set newstuff [lsort $mystuff]
puts [join $newstuff \n]
 
puts "-------------------------"
 
puts "Sorts ONLY by date."
# Appears to keep identically ranked records in ORIGINAL order
set newstuff [lsort -command first $mystuff]
puts [join $newstuff \n]

The lsort command sorts a list, returning a new list, and lsort -command does the same thing but allows the user to specify a proc which returns a negative, zero or positive value to indicate which of the records comes first (negative = no swap, positive = swap, zero = don't care). You'll note that it appears that Tcl provides a naturally stable sort in these circumstances, with and zero returns causing the output records to remain in their original order. I have seen no proof of this - the comment is empirical, but I have swapped by data lines around, and added and taken a few away, and it appears to hold.

Sorting in Perl

Here is the sample code to demonstrate those various sorts in Perl:


@mystuff = ("20070903 John Smith etc",
"20070901 Bill Jones",
"20070902 Arthur Clark",
"20070903 George Hill",
"20070902 Arthur Dent",
"20070903 Petal Honour-Flower");
 
print "Initial order\n";
print (join("\n",@mystuff),"\n");
print "-------------------------\n";
 
print "Sort by Forename within date\n";
@newstuff = sort(@mystuff);
print (join("\n",@newstuff),"\n");
print "-------------------------\n";
 
print "Sort by date ONLY\n";
@newstuff = sort bydate (@mystuff);
print (join("\n",@newstuff),"\n");
print "-------------------------\n";
 
sub bydate {
@a = split(/\s+/,$a);
@b = split(/\s+/,$b);
return $a[0] <=> $b[0];
}

The principles are very similar to those of Tcl, but the langauge is very different. Again, this appears to be a stable sort automatically.
(written 2007-09-06 17:16:10)

 P211 - Perl - Hashes
T206 - Tcl/Tk - Lists
T214 - Tcl/Tk - Other Facilities in Tcl

Back to Kasteel Elsloo - Michelin rated hotel.

Previous and next or Horse's mouth home

Forward to Expanding a grid - Tcl/Tk

Handling Binary data in Tcl (with a note on C)
A series of tyre damages
Ignore case in Regular Expression
Expanding a grid - Tcl/Tk
Stable sorting - Tcl, Perl and others
Kasteel Elsloo - Michelin rated hotel.
Melksham Hotel - Five Star Kitchen!
MySQL joins revisited
While waiting for Melksham Post Office
Subway Restaurant in Melksham, Wiltshire
Link to page ... 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 at 50 posts per page


This is a page archived from The Horse's Mouth at http://www.wellho.net/horse/ - the diary and writings of Graham Ellis. Every attempt was made to provide current information at the time the page was written, but things do move forward in our business - new software releases, price changes, new techniques. Please check back via our main site for current courses, prices, versions, etc - any mention of a price in "The Horse's Mouth" cannot be taken as an offer to supply at that price.

Link to Ezine home page (for reading).
Link to Blogging home page (to add comments).