Sorting tables with no garbage (table.sort alternatives)

[Iza]

Hi all,
if you need to sort tables quite frequently you'll find that table.sort causes a lot of garbage memory. Here are two memory friendly in-place alternatives (parameter compatible to table.sort). Maybe some people finding this helpful:

1. Shell sort (around 1/3 slower than table.sort which is a quick sort implementation in lua):

local tIncrements = {
	1391376, 463792, 198768, 86961, 33936,
	13776, 4592, 1968, 861, 336,
	112, 48, 21, 7, 3, 1
};

--
local tInc;
local tSwap;
local tCnt0, tCnt, tCnt2;
local tSize;
local tVal;
local tVal2;
function shellSort(aTable, aValidator)
  for tCnt0 = 1, #tIncrements do
    tInc = tIncrements[tCnt0];
    for tCnt = tInc + 1, #aTable do
      tVal = aTable[tCnt];

      for tCnt2 = tCnt - tInc, 1, -tInc do
        tVal2 = aTable[tCnt2];
        if (not aValidator(tVal, tVal2)) then
          break;
        end

        aTable[tCnt] = tVal2;
        tCnt = tCnt2;
      end
      aTable[tCnt] = tVal;
    end
  end
end

For tables which most likely are sorted already (or close to being sorted) even good old bubble sort can be very fast:

local tCnt, tCnt2, tSize;
local tVal1, tVal2;
local tIsSwapped;
function bubbleSort(aTable, aValidator)
	tSize = #aTable - 1;
	for tCnt = 1, tSize do

		tIsSwapped = false;
		for tCnt2 = tCnt, tSize do
			tVal1 = aTable[tCnt2];
			tVal2 = aTable[tCnt2 + 1];
			if (not aValidator(tVal1, tVal2)) then
				aTable[tCnt2] = tVal2;
				aTable[tCnt2 + 1] = tVal1;
				tIsSwapped = true;
			end
		end

		if (not tIsSwapped) then
			return;
		end
	end
end

[Torhal]

The only time table.sort() should be causing "garbage memory" is if you are creating a new sort function every time you call it instead of re-using a single function.

Bad:

table.sort(my_table, function(a, b)
                                if a.name < b.name then
                                    return true
                                else
                                    return false
                                end
                             end)

Good:

local function MySortFunction(a, b)
    if a.name < b.name then
        return true
    else
        return false
    end
end

table.sort(my_table, MySortFunction)

[Iza]

Yes, you're perfectly right, thank you...

[Xinhuan]

Gooder:

local function MySortFunction(a, b)
    return a.name < b.name
end

table.sort(my_table, MySortFunction)

[Torhal]

Indeed. :P