Comparing and Sorting Strings

Part I · Module 4 · Chapter 4.11 · Comparing and Sorting Strings

1. Comparing: What You Already Have

Three operators from Module 3 do all the text comparison there is:

use strict;
use warnings;

my ($a_val, $b_val) = ("PASS", "pass");

printf "eq            : %s\n", ($a_val eq $b_val ? "true" : "false");
printf "ne            : %s\n", ($a_val ne $b_val ? "true" : "false");
printf "cmp           : %d\n", ($a_val cmp $b_val);
printf "lc eq lc      : %s\n", (lc($a_val) eq lc($b_val) ? "true" : "false");

eq            : false
ne            : true
cmp           : -1
lc eq lc      : true

• eq / ne answer yes or no — Chapter 3.5.
• cmp answers which comes first, as -1, 0 or 1 — Chapter 3.7.
• Lowercasing both sides makes the comparison case-insensitive, using Chapter 4.6's lc.

"PASS" cmp "pass" is -1, so "PASS" comes first. That single fact is the whole explanation for the next section.

2. A Plain Sort Separates the Cases

use strict;
use warnings;

my @blocks = ("fifo", "ALU_top", "alu", "Decoder", "regfile");

print "default      : ", join(" ", sort @blocks),                      "\n";
print "explicit cmp : ", join(" ", sort { $a cmp $b } @blocks),         "\n";
print "fold case    : ", join(" ", sort { lc($a) cmp lc($b) } @blocks), "\n";
print "descending   : ", join(" ", sort { $b cmp $a } @blocks),         "\n";
print "reverse sort : ", join(" ", reverse sort @blocks),               "\n";

default      : ALU_top Decoder alu fifo regfile
explicit cmp : ALU_top Decoder alu fifo regfile
fold case    : alu ALU_top Decoder fifo regfile
descending   : regfile fifo alu Decoder ALU_top
reverse sort : regfile fifo alu Decoder ALU_top

Four things in that output.

The default sort is cmp. Rows 1 and 2 are identical, so sort @list and sort { $a cmp $b } @list are the same thing. Chapter 3.6 §3 made the related point that this is also true for numbers, which is why a list of numbers sorts as text unless you say otherwise.

Every capitalised name precedes every lowercase one. ALU_top and Decoder come first, then alu, fifo, regfile. Not interleaved — two groups. Uppercase letters are code points 65–90 and lowercase are 97–122, so this is ordering by character code working exactly as specified.

Folding the case interleaves them. sort { lc($a) cmp lc($b) } gives alu ALU_top Decoder fifo regfile, which is the order a human would call alphabetical.

sort { $b cmp $a } and reverse sort agree. Both give descending order. reverse sort reads more clearly; { $b cmp $a } is one pass instead of two and is the form you need when the comparator is doing something else as well.

$a and $b are the two variables sort sets for each comparison. They belong to Module 6 along with sort itself; here they are the mechanism the comparator block uses.

3. An Underscore Sorts After Every Uppercase Letter

This one is directly relevant to this trade, because every signal and block name has underscores in it.

use strict;
use warnings;

for my $c ("-", ".", "0", "A", "X", "_", "a", "~") {
    printf "%-3s ord=%d\n", $c, ord($c);
}

print "\nsorted: ", join(" ", sort ("alu_top", "alu-top", "alu.top", "aluXtop")), "\n";

-   ord=45
.   ord=46
0   ord=48
A   ord=65
X   ord=88
_   ord=95
a   ord=97
~   ord=126

sorted: alu-top alu.top aluXtop alu_top

alu_top sorted last, after aluXtop.

The reason is in the table above it: _ is code point 95 and X is 88. Since the first three characters are identical, the comparison is decided on the fourth, and 95 is greater than 88.

So the ordering of punctuation relative to letters is:

This is why a sorted list of mixed names can look shuffled: alu_top, aluTop and alu-top sort in an order that has nothing to do with how you read them. It is the same character-by-character rule Chapter 3.6 §2 and §4 established, now with the numbers that make the result predictable.

4. Case-Folding Creates Ties

The case-insensitive comparator has a consequence worth knowing before you rely on it.

use strict;
use warnings;

my @names = ("alu", "ALU", "Alu");

print "fold only     : ", join(" ", sort { lc($a) cmp lc($b) } @names),              "\n";
print "fold then cmp : ", join(" ", sort { lc($a) cmp lc($b) or $a cmp $b } @names), "\n";

fold only     : alu ALU Alu
fold then cmp : ALU Alu alu

Under lc($a) cmp lc($b), all three names compare equal — lc makes every one of them alu. So the comparator returns 0 for every pair, and their relative order in the output is simply whatever the sort left them in. Here that happened to be the input order; it is not something to depend on.

Adding or $a cmp $b breaks the tie by comparing the original strings, which gives a definite and repeatable order: ALU, Alu, alu — uppercase first, by the rule from §2.

This is Chapter 3.7 §3's tie-break idiom arriving where it is genuinely needed. It works because cmp returns 0 on a tie and 0 is false, so the or falls through to the second comparison — and or binds loosely enough, by Chapter 3.8 §5, that the comparator reads correctly without parentheses.

5. The Problems Carried In From Earlier Chapters

Two failures that look like sorting bugs and are not.

Numbers sorted as text — Chapter 3.6 §3, restated because it is the most common one:

use strict;
use warnings;

my @counts = ("10", "9", "100", "2");

print "sort       : ", join(" ", sort @counts),                "\n";
print "sort <=>   : ", join(" ", sort { $a <=> $b } @counts),   "\n";

sort       : 10 100 2 9
sort <=>   : 2 9 10 100

10 100 2 9 is correct text ordering and wrong for a column of counts. If the values are quantities, the comparator must be <=>.

Untrimmed values — Chapter 4.6 §3:

use strict;
use warnings;

my @status = ("PASS", "PASS ", "FAIL");

print "as-is   : [", join("][", sort @status), "]\n";

my @trimmed = map { my $v = $_; $v =~ s/^\s+|\s+$//g; $v } @status;

print "trimmed : [", join("][", sort @trimmed), "]\n";

as-is   : [FAIL][PASS][PASS ]
trimmed : [FAIL][PASS][PASS]

"PASS" and "PASS " are two different values and sort as two entries, which in a grouped report means two rows for one status. Normalising first — the discipline from Chapter 4.6 §6 — is what prevents it.

map is Module 6's; it appears here only to apply the trim to each element in one line.

6. Choosing a Comparator

The first row is the one worth memorising, because it is the common case for a report of block or test names and it is correct rather than merely nearly correct.

use strict;
use warnings;

my @blocks = ("fifo", "ALU_top", "alu", "Decoder", "regfile");

for my $b (sort { lc($a) cmp lc($b) or $a cmp $b } @blocks) {
    print "$b\n";
}

alu
ALU_top
Decoder
fifo
regfile

Human-alphabetical, deterministic, and five words of comparator.

7. Why This Matters in Engineering Work

A report's row order is part of its readability. A list of blocks that jumps from ALU_top to Decoder to alu reads as unsorted, and a reader who cannot find an entry assumes it is absent. The case-folding comparator costs nothing and removes the question.

Underscores make the default order genuinely confusing. Signal and block names in this trade are full of them, and _ sitting between the uppercase and lowercase ranges means names that differ only in a separator can land far apart. Knowing the code point is what turns "the sort is broken" into "the sort is doing what I asked".

Unbroken ties create diff noise. A nightly report diffed against yesterday's shows rows moving for no reason, and the real change is lost in it. A total comparator makes the output reproducible, which is what makes the diff useful.

And the two imported problems account for most real complaints. "The sort is wrong" is usually either numbers being compared as text or values that were never normalised. Both are fixed before the sort, not inside it.

8. Common Mistakes

Expecting the default sort to be case-insensitive. It is cmp, so uppercase comes first in a block.

Expecting it to be alphabetical. It is character order, and _ is 95 — after uppercase, before lowercase.

Folding case without a tie-break. Entries differing only in case compare equal and their order is unspecified.

Sorting numbers without <=>. 10 sorts before 9.

Sorting untrimmed or mixed-case values. They sort as distinct entries, giving duplicate rows for one logical value.

Assuming sort reorders the array. It returns a new list. Assign it back if you want the array changed.

Writing reverse sort { $b cmp $a }. The two reversals cancel. Pick one.

9. Exercise

Exercise 1 — the four orders. Run the §2 script and record all five lines. Then say which two are identical and why, and which two are identical and why.

Exercise 2 — the underscore. Print the code points of X, _ and a. Then sort ("sig_a", "sigXa", "sig-a", "sigza") and explain the resulting order using only those numbers.

Exercise 3 — the tie. Sort ("fifo", "FIFO", "Fifo") with lc($a) cmp lc($b) and then with the tie-break added. Record both orders and say which one you could rely on across runs.

Exercise 4 — alphabetical for humans. Take the list ("regfile", "ALU", "decoder_top", "Fifo_wr", "alu") and produce the order a person would call alphabetical, deterministically. Write the comparator you used and justify each half of it.

Exercise 5 — numbers again. Sort ("7", "70", "7000", "8") as text and as numbers. Record both and say which you would put in a report column headed "cycles".

Exercise 6 — the duplicate row. Build a list containing "PASS", "PASS " and "pass", sort it, and print the result with each element in brackets. Then normalise first and sort again. Report how many distinct entries each version has, and what that means for a count-by-status report.

Exercise 7 — does sort modify? Declare an array, sort it into a second array, then print both. State what the output proves and give the one-line change that would reorder the original.

Exercise 8 — reproducibility. Explain, in two or three sentences, why a report sorted with an incomplete comparator causes trouble in a flow that diffs today's output against yesterday's — and what the one-clause fix is.

10. Summary

• eq and ne answer yes or no; cmp answers which comes first — Module 3's operators, applied to text.
• The default sort is cmp, so sort @list and sort { $a cmp $b } @list are identical.
• Every capitalised name precedes every lowercase one, because uppercase is 65–90 and lowercase is 97–122.
• _ is code point 95 — after all uppercase letters, before all lowercase — so alu_top sorts after aluXtop.
• sort { lc($a) cmp lc($b) } gives human-alphabetical order and creates ties between entries differing only in case.
• An unbroken tie has unspecified order. Add or $a cmp $b to make the result reproducible and the diffs meaningful.
• sort returns a new list and leaves the original array untouched.
• Numbers need <=>, and padded or mixed-case values need normalising before the sort, not inside it.

That closes Module 4. You can now write a string in either quoting form and know what each does to it, interpolate a value safely, measure and slice text without pattern matching, normalise a parsed field, split a line into fields and rebuild it faithfully, format a column-aligned report, strip a line ending correctly on either platform, hold multi-line text in one statement, and order a list of names the way a person expects.

Module 5 turns to holding more than one value at a time — arrays, which several chapters here have been quietly borrowing — and gives them the chapter-length treatment this module gave to text.