Training, Open Source Programming Languages

This is page http://www.wellho.net/mouth/1334_Sta ... thers.html

Our email: info@wellho.net • Phone: 01225 708225

 
Python and Tcl - public course schedule [here]
Private courses on your site - see [here]
Please ask about maintenance training for Perl, PHP, Lua, etc
 
Stable sorting - Tcl, Perl and others

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)

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

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

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


Back to
Kasteel Elsloo - Michelin rated hotel.
Previous and next
or
Horse's mouth home
Forward to
Expanding a grid - Tcl/Tk
Some other Articles
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
4759 posts, page by page
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, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96 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).

© WELL HOUSE CONSULTANTS LTD., 2019: 404 The Spa • Melksham, Wiltshire • United Kingdom • SN12 6QL
PH: 01225 708225 • EMAIL: info@wellho.net • WEB: http://www.wellho.net • SKYPE: wellho

PAGE: http://www.wellho.net/mouth/1334_Sta ... thers.html • PAGE BUILT: Sat May 27 16:49:10 2017 • BUILD SYSTEM: WomanWithCat