Can't sort table with associative indexes

Question

Hi, why I can't use table.sort to sort tables with associative indexes?

Answer 1

Because they don't have any order in the first place. It's like trying to sort a garbage bag full of bananas.

Answer 2

In general, Lua tables are pure associative arrays. There is no "natural" order other than the as a side effect of the particular hash table implementation used in the Lua core. This makes sense because values of any Lua data type (other than nil) can be used as both keys and values; but only strings and numbers have any kind of sensible ordering, and then only between values of like type.

For example, what should the sorted order of this table be:

unsortable = {
    answer=42,
    true="Beauty",
    [function() return 17 end] = function() return 42 end,
    [math.pi] = "pi",
    [ {} ] = {},
    12, 11, 10, 9, 8
}

It has one string key, one boolean key, one function key, one non-integral key, one table key, and five integer keys. Should the function sort ahead of the string? How do you compare the string to a number? Where should the table sort? And what about userdata and thread values which don't happen to appear in this table?

By convention, values indexed by sequential integers beginning with 1 are commonly used as lists. Several functions and common idioms follow this convention, and table.sort is one example. Functions that operate over lists usually ignore any values stored at keys that are not part of the list. Again, table.sort is an example: it sorts only those elements that are stored at keys that are part of the list.

Another example is the # operator. For the above table, #unsortable is 5 because unsortable[5] ~= nil and unsortable[6] == nil. Notice that the value stored at the numeric index math.pi is not counted even though pi is between 3 and 4 because it is not an integer. Furthermore, none of the other non-integer keys are counted either. This means that a simple for loop can iterate over the entire list:

for i in 1,#unsortable do
    print(i,unsortable[i])
end

Although that is often written as

for i,v in ipairs(unsortable) do
    print(i,v)
end

In short, Lua tables are unordered collections of values, each indexed by a key; but there is a special convention for sequential integer keys beginning at 1.

Edit: For the special case of non-integral keys with a suitable partial ordering, there is a work-around involving a separate index table. The described content of tables keyed by string values is a suitable example for this trick.

First, collect the keys in a new table, in the form of a list. That is, make a table indexed by consecutive integers beginning at 1 with keys as values and sort that. Then, use that index to iterate over the original table in the desired order.

For example, here is foreachinorder(), which uses this technique to iterate over all values of a table, calling a function for each key/value pair, in an order determined by a comparison function.

function foreachinorder(t, f, cmp)
    -- first extract a list of the keys from t
    local keys = {}
    for k,_ in pairs(t) do
        keys[#keys+1] = k
    end
    -- sort the keys according to the function cmp. If cmp
    -- is omitted, table.sort() defaults to the < operator
    table.sort(keys,cmp)
    -- finally, loop over the keys in sorted order, and operate
    -- on elements of t
    for _,k in ipairs(keys) do
        f(k,t[k])
    end
end

It constructs an index, sorts it with table.sort(), then loops over each element in the sorted index and calls the function f for each one. The function f is passed the key and value. The sort order is determined by an optional comparison function which is passed to table.sort. It is called with two elements to compare (the keys to the table t in this case) and must return true if the first is less than the second. If omitted, table.sort uses the built-in < operator.

For example, given the following table:

t1 = {
    a = 1,
    b = 2,
    c = 3,
}

then foreachinorder(t1,print) prints:

a    1
b    2
c    3

and foreachinorder(t1,print,function(a,b) return a>b end) prints:

c    3
b    2
a    1

Answer 3

You can only sort tables with consecutive integer keys starting at 1, i.e., lists. If you have another table of key-value pairs, you can make a list of pairs and sort that:

function sortpairs(t, lt)
  local u = { }
  for k, v in pairs(t) do table.insert(u, { key = k, value = v }) end
  table.sort(u, lt)
  return u
end

Of course this is useful only if you provide a custom ordering (lt) which expects as arguments key/value pairs.

This issue is discussed at greater length in a related question about sorting Lua tables.