WoWInterface - View Single Post - Sorting tables with no garbage (table.sort alternatives)
 View Single Post
07-05-11, 10:41 AM   #1
Iza
A Cyclonian
Join Date: May 2009
Posts: 43
Sorting tables with no garbage (table.sort alternatives)

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):

Code:
```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:

Code:
```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```