lsort: Sorting by the Right Key

Part I · Module 6 · Chapter 6.10 · lsort

1. The Bug, First

puts [lsort {10 9 100}]

Predict that before reading on.

10 100 9

Not 9 10 100. The default sort is textual, so it compared character by character: 1 before 9, and 10 before 100 because it is shorter.

That is a correct alphabetical ordering and a useless numeric one. And note what it is not — an error. The script runs, the output looks like a sorted list, and the order is wrong.

puts [lsort -integer {10 9 100}]

9 10 100

2. The Comparison Modes

puts "-ascii   -> [lsort -ascii {banana apple cherry}]"
puts "-integer -> [lsort -integer {10 9 100}]"
puts "-real    -> [lsort -real {1.5 1.25 10.1}]"

-ascii   -> apple banana cherry
-integer -> 9 10 100
-real    -> 1.25 1.5 10.1

-ascii is the default and sorts by character code. -integer and -real sort numerically.

There is also -dictionary, which sorts case-insensitively and treats runs of digits as numbers — useful for names like item2 and item10:

puts "-ascii      -> [lsort -ascii {item10 item2 item1}]"
puts "-dictionary -> [lsort -dictionary {item10 item2 item1}]"

-ascii      -> item1 item10 item2
-dictionary -> item1 item2 item10

That is often exactly what a person expects from a list of names with numbers in them.

3. Direction and Duplicates

puts "-decreasing -> [lsort -decreasing -integer {10 9 100}]"
puts "-unique     -> [lsort -unique {b a b c a}]"
puts "both        -> [lsort -unique -decreasing {b a b c a}]"

-decreasing -> 100 10 9
-unique     -> a b c
both        -> c b a

-unique removes duplicates as it sorts, which makes lsort -unique the standard way to deduplicate a list. There is no separate command for it.

4. Case

set l {apple Banana cherry}

puts "plain   -> [lsort $l]"
puts "-nocase -> [lsort -nocase $l]"

plain   -> Banana apple cherry
-nocase -> apple Banana cherry

The plain sort put Banana first because B has a lower character code than a — Chapter 5.6 §7. -nocase gives the order a person would expect.

This is the same decision as Chapter 5.7 §4: either pass the option every time, or normalise the data once.

5. Sorting a Table by a Column

-index sorts nested lists by one element of each:

set rows {{clk 3} {reset 1} {payload 2}}

puts "by name  -> [lsort -index 0 $rows]"
puts "by number-> [lsort -index 1 -integer $rows]"

by name  -> {clk 3} {payload 2} {reset 1}
by number-> {reset 1} {payload 2} {clk 3}

Note the second one needs both -index 1 and -integer — -index says which element to compare, and the comparison mode still has to be right. Leaving -integer off would sort the numbers as text, which is §1 again, hidden one level deeper.

This is the standard way to order a table of records, and it combines with Chapter 6.11.

6. Sorting by Something Computed

When none of the built-in modes expresses your order, -command takes a procedure that compares two elements:

proc by_length {a b} {
    return [expr {[string length $a] - [string length $b]}]
}

puts [lsort -command by_length {ccc a bb dddd}]

a bb ccc dddd

The procedure must return a negative number, zero, or a positive number — exactly the three-way answer string compare produces, which is what that command is for.

proc is Module 10; the shape is here because -command is the escape hatch when the built-in modes are not enough.

7. It Returns a New List

set l {c a b}

lsort $l
puts "unchanged: $l"

set l [lsort $l]
puts "stored:    $l"

unchanged: c a b
stored:    a b c

Like almost everything in this module — Chapter 6.7 §2 — it hands back a new list. Store it.

8. A Worked Example

set results {
    {payload 64}
    {clk 1}
    {reset 1}
    {addr 32}
}

puts "widest first:"
foreach row [lsort -index 1 -integer -decreasing $results] {
    puts [format "  %-10s %4d" {*}$row]
}

set widths {}
foreach row $results {
    lappend widths [lindex $row 1]
}
puts "distinct widths: [lsort -unique -integer $widths]"

widest first:
  payload      64
  addr         32
  clk           1
  reset         1
distinct widths: 1 32 64

Three options on one sort — which column, how to compare it, and which direction — and then -unique -integer to collapse the widths.

The {*}$row spreads each row's two elements into format's two arguments; that is Chapter 6.13.

9. Common Mistakes

Sorting numbers without -integer or -real. §1. The big one.

Forgetting the comparison mode when using -index. §5.

Forgetting to store the result. §7.

Expecting case-insensitive order by default. §4.

Writing a loop to deduplicate. lsort -unique. §3.

Using -ascii on names containing numbers. -dictionary is usually what a person means. §2.

10. Exercises

Exercise 1 — the bug. Sort {2 10 1 20} with and without -integer. Write down both results and explain the first.

Exercise 2 — modes. Sort {1.5 1.25 10.1} three ways: default, -real, and -integer. What happens with the third, and why?

Exercise 3 — names with numbers. Sort {run10 run2 run1} with -ascii and with -dictionary. Which would you show a user?

Exercise 4 — deduplicate. From {b a c a b b}, produce a sorted list of unique values, then the same in reverse order.

Exercise 5 — a table. Given four rows of name and size, print them sorted by name, then by size descending.

Exercise 6 — by length. Sort a list of words by length using -command. Then say what happens to two words of equal length.

11. Remember

• The default sort is textual. lsort {10 9 100} gives 10 100 9.
• Pass -integer or -real for numbers, every time. The wrong order is plausible, not an error.
• -ascii is the default; -dictionary is case-insensitive and handles embedded numbers the way people expect.
• -decreasing reverses; -unique deduplicates — and is the standard way to do so.
• -nocase for case-insensitive order, or normalise once instead.
• -index N sorts nested lists by one column — and still needs the right comparison mode.
• -command takes a procedure returning negative, zero or positive.
• It returns a new list. Store it.

Next: the structure -index has been operating on.