Thread Tools Display Modes
Prev Previous Post   Next Post Next
Unread 07-05-11, 10:41 AM   #1
Iza
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):

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