Quantcast Sorting tables with no garbage (table.sort alternatives) - WoWInterface
Thread Tools Display Modes
Prev Previous Post   Next Post Next
Unread 07-05-11, 10:41 AM   #1
A Cyclonian
AddOn Author - Click to view addons
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):

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

        aTable[tCnt] = tVal2;
        tCnt = tCnt2;
      aTable[tCnt] = tVal;
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;

		if (not tIsSwapped) then
Iza is offline   Reply With Quote

Go BackWoWInterface » Developer Discussions » Tutorials & Other Helpful Info. » Sorting tables with no garbage (table.sort alternatives)

Thread Tools
Display Modes

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