How do I sort a table while keeping a record of the original positions?

Question

I have a Lua table of integers which I sort in ascending order. Later on, my script need to take the index of the smallest number (that is, the position it was on originally, before sorting), try something, then move on to the index of the second smallest number, try something, etc. until the end of the sorted list.

My problem is that I obviously lose the original positions (or indexes) of my original table when I sort it. Is there a way, maybe with a nested table holding both numbers and indexes, to keep a record of the original indexes, and then perform a sort on the integers?

To make the question a little bit clearer:

Original table: 4 6 2

Sorted table: 2 4 6

In this sorted table, I need to know that 2 was at the position 3 before sorting, that 4 was at position 1, and that 6 was at position 2.

Answer 1

Something like the following (untested code written in answer box) should work regardless of uniqueness (though lua table sorting isn't stable so you can't guarantee which of equal elements will be sorted first in case that matters):

local origtab = {4, 6, 2}
local sorttab = {}
for i,v in ipairs(origtab) do
    sorttab[i] = {index = i, value = v}
end
table.sort(sorttab, function(a, b) return a.value < b.value end)
for i,t in ipairs(sorttab) do
    -- t.index is original index
    -- t.value is value
end

Answer 2

If all of your values are guaranteed to be unique, then this is pretty simple.

local function remember_sort(t)
  local map = {}
  for i=1, #t do map[t[i]] = i end
  table.sort(t)
  return map -- map of values to old indices
end

local t = {4, 6, 2}
local r = remember_sort(t)

for k, v in pairs(r) do print(k, v) end

2       3
4       1
6       2