CODEWITHSUNDEEP
tcl
arijit
arijit

Reputation: 67

TCL lsort not making sense for integers

I am confused on what sorting algorithm lsort uses. I have a list of list (coordinate points) say:

set a { {142 250} {142 99} }

Then, lsort -uniq $a gives output: {142 250} {142 99}

and I was expecting it to be the other way round: {142 99} {142 250}

Please clear my confusion as what is going on here?

Upvotes: 1

Views: 1465

Answers (3)

Schelte Bron
Schelte Bron

Reputation: 4813

Tcl uses a stable sort algorithm. If you want a list of coordinate points to be sorted by their x-coordinate, and for equal x-coordinates by y-coordinate, you sort by y-coordinate first and then by x-coordinate.

You can't filter out duplicate coordinate points this way. If that is a requirement, then first perform an lsort -unique on the whole list (assuming the coordinate points are canonical lists all using the same number base). Beware that this does cause shimmering from list to string and back. So if you care about performance, you may want to remove duplicates using a different technique. This should be easy because after sorting, duplicates will be next to eachother.

set a { {142 250} {142 99} {83 250} }
puts [lsort -integer -index 0 [lsort -integer -index 1 $a]]
# ==> {83 250} {142 99} {142 250}

Upvotes: 1

Donal Fellows
Donal Fellows

Reputation: 137587

The sorting is that order because 142 250 is less than 142 99 according to the rules of string compare (the first 4 characters are the same, and the fifth is ordered that way). This is because lsort uses string comparison by default.

Your options are to either change the rule for selecting which part of each word in the list to use as the key (the default is to use the whole word) using -index, or to switch to a different comparison rule such as -dictionary or -integer.

set a { {142 250} {142 99} {142 -17} {142 0x1f} }
puts [lsort -integer -index 1 $a]
# ==> {142 -17} {142 0x1f} {142 99} {142 250}

set a { {142 250} {142 99} {142 -17} {142 0x1f} }
puts [lsort -dictionary $a]
# ==> {142 -17} {142 0x1f} {142 99} {142 250}

Be careful! Understand what these do before choosing one. (The -dictionary option is a “guess at how to sort things for people” rule that can surprise you if used for anything else. But it's brilliant for sorting things for showing to users.)

Upvotes: 3

Ruslan Rakhmanin
Ruslan Rakhmanin

Reputation: 393

If you need to sort list by the second coordinate you can use this code

set a { {142 250} {142 99} }
lsort -integer -index 1 $a

By default, TCL see all as string. So, if need to sort as integer, you should explicitly specify it.

But if you need to sort your points by coordinates one by one (if X coordinates are equal -- sort by Y, if X and Y are equal -- sort by Z and so on), you need to use -command in lsort probably.

proc compare {a b} {
  foreach ai $a bi $b {
    if {$ai < $bi} {
        return -1
    } elseif {$ai > $bi} {
        return 1
    }
  }
  return 0
}
set a { {142 250} {153 99} {142 99}}
lsort -command compare $a
# >> {142 99} {142 250} {153 99}

set b { {142 250 12} {142 99 9} {153 99 1} {142 99 10}}
lsort -command compare $b
# >> {142 99 9} {142 99 10} {142 250 12} {153 99 1}

Upvotes: 1

Related Questions