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, updated 2007-09-07)

 T214 - Tcl/Tk - Other Facilities in Tcl
  [239] What and why for the epoch - (2005-03-08)
  [364] pu daily and p hourly - (2005-06-30)
  [366] Error handling in Tcl through catch - (2005-07-02)
  [461] Shortened interactive commands - (2005-10-11)
  [748] Getting rid of variables after you have finished with them - (2006-06-06)
  [782] Converting between Hex and Decimal in Tcl - (2006-06-28)
  [1277] AgtInvoke - a command to drive Agilent Tcl software extensions - (2007-07-26)
  [1338] Handling Binary data in Tcl (with a note on C) - (2007-09-09)
  [2467] Tcl - catching an error before your program crashes - (2009-10-22)
  [3287] Exceptions - Tcl style - (2011-05-12)
  [3570] Trapping errors in Tcl - the safety net that catch provides - (2012-01-06)
  [3583] Expanding a list of parameters in Tcl - {*} and eval - (2012-01-17)
  [4207] Exception handling in Tcl - (2013-11-14)
  [4523] Catching failed commands and not crashing the program in Tcl - (2015-10-10)
  [4525] What does Tcl do if you try to run a command that is not defined? - (2015-10-10)
  [4762] Coverage map in Tcl - how many times has each proc been called? - (2017-09-28)

T206 - Tcl/Tk - Lists
  [144] Tcl sandwich - lists in Tcl - (2004-12-08)
  [463] Splitting the difference - (2005-10-13)
  [781] Tcl - lappend v concat - (2006-06-27)
  [1282] Stringing together Tcl scripts - (2007-07-29)
  [1283] Generating traffic for network testing - (2007-07-29)
  [1402] Tcl - append v lappend v concat - (2007-10-23)
  [1405] Sorting in Tcl - lists and arrays - (2007-10-24)
  [1601] Replacing the last comma with an and - (2008-04-04)
  [2468] What are Tcl lists? - (2009-10-22)
  [2472] split and join in tcl and expect - (2009-10-23)
  [3285] Extracting data from a string / line from file - Tcl - (2011-05-10)
  [3394] The difference between lists and strings - Tcl - (2011-08-16)
  [3415] User defined sorting and other uses of callbacks in Tcl and Tk - (2011-09-02)
  [3582] Tcl collections - lists, dicts and array - (2012-01-16)
  [3618] lists and struct::list in Tcl - Introduction to struct::list and examples - (2012-02-18)
  [4209] Lists in Tcl - fundamentals in a commented source code example - (2013-11-16)
  [4454] Everything is a string - even a list - (2015-03-11)
  [4455] Working out distance between places, using OS grid references and a program in Tcl - (2015-03-11)

P211 - Perl - Hashes
  [240] Conventional restraints removed - (2005-03-09)
  [386] What is a callback? - (2005-07-22)
  [738] (Perl) Callbacks - what are they? - (2006-05-30)
  [930] -> , >= and => in Perl - (2006-11-18)
  [968] Perl - a list or a hash? - (2006-12-06)
  [1705] Environment variables in Perl / use Env - (2008-07-11)
  [1826] Perl - Subs, Chop v Chomp, => v , - (2008-10-08)
  [1856] A few of my favourite things - (2008-10-26)
  [1917] Out of memory during array extend - Perl - (2008-12-02)
  [2833] Fresh Perl Teaching Examples - part 2 of 3 - (2010-06-27)
  [2836] Perl - the duplicate key problem explained, and solutions offered - (2010-06-28)
  [2915] Looking up a value by key - associative arrays / Hashes / Dictionaries - (2010-08-11)
  [2920] Sorting - naturally, or into a different order - (2010-08-14)
  [3042] Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl - (2010-11-11)
  [3072] Finding elements common to many lists / arrays - (2010-11-26)
  [3106] Buckets - (2010-12-26)
  [3400] $ is atomic and % and @ are molecular - Perl - (2011-08-20)
  [3451] Why would you want to use a Perl hash? - (2011-09-20)
  [3662] Finding all the unique lines in a file, using Python or Perl - (2012-03-20)

Back to Kasteel Elsloo - Michelin rated hotel.

Previous and next or Horse's mouth home

Forward to Expanding a grid - Tcl/Tk

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