Sorting tables with no garbage (table.sort alternatives) - WoWInterface
 Thread Tools Display Modes
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```

07-05-11, 11:50 AM   #2
Torhal
A Pyroguard Emberseer

Join Date: Aug 2008
Posts: 1,134
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.

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

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

table.sort(my_table, MySortFunction)```
__________________
Whenever someone says "pls" because it's shorter than "please", I say "no" because it's shorter than "yes".

Author of Revelation, Spamalyzer, TravelAgent, Volumizer, and many other AddOns.

07-06-11, 02:28 AM   #3
Iza
A Cyclonian
Join Date: May 2009
Posts: 43
Yes, you're perfectly right, thank you...

Last edited by Iza : 07-06-11 at 04:50 AM.

07-09-11, 12:54 AM   #4
Xinhuan
A Chromatic Dragonspawn

Join Date: Feb 2007
Posts: 173
Gooder:
Code:
```local function MySortFunction(a, b)
return a.name < b.name
end

table.sort(my_table, MySortFunction)```
__________________
Author of Postal, Omen3, GemHelper, BankItems, WoWEquip, GatherMate, GatherMate2, Routes and Cartographer_Routes

07-09-11, 05:30 AM   #5
Torhal
A Pyroguard Emberseer

Join Date: Aug 2008
Posts: 1,134
Indeed. :P
__________________
Whenever someone says "pls" because it's shorter than "please", I say "no" because it's shorter than "yes".

Author of Revelation, Spamalyzer, TravelAgent, Volumizer, and many other AddOns.

 WoWInterface » Sorting tables with no garbage (table.sort alternatives)

 Thread Tools Display Modes Hybrid Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off