208
« on: February 25, 2017, 04:30:07 AM »
Long time ago I made this quick sort for records.
// Quick sort implementation
function QuickSortRecord(%list, %func, %left, %right)
{
// Standard function
if (!isFunction(%func))
%func = getMax;
// Avoid crash
%size = getRecordCount(%list);
%right = mClamp(%right, 0, %size - 1);
%left = mClamp(%left, 0, %size - 1);
// Nothing to compare
if (%right <= %left)
return %list;
// There could be a implementation of median-of-three,
// but it is hard due of how TorqueScript is built up.
%pivotIndex = mFloor((%left + %right) / 2);
%pivotNextIndex = %left;
// Partition
%pivotValue = getRecord(%list, %pivotIndex);
%list = swapRecord(%list, %pivotIndex, %right);
%storeIndex = %left;
for (%i = %left; %i < %right; %i++)
{
%a = Call(%func, getRecord(%list, %i), %pivotValue);
if (%a < 0)
{
%list = swapRecord(%list, %i, %pivotNextIndex);
%pivotNextIndex++;
}
}
%list = swapRecord(%list, %pivotNextIndex, %right);
// Continue on next
%list = QuickSortRecord(%list, %func, %left, %pivotNextIndex - 1);
%list = QuickSortRecord(%list, %func, %pivotNextIndex + 1, %right);
return %list;
}
// Swap data in record list
function swapRecord(%list, %first, %second)
{
// Avoid crash
%size = getRecordCount(%list);
%first = mClamp(%first, 0, %size - 1);
%second = mClamp(%second, 0, %size - 1);
%a = getRecord(%list, %first);
%b = getRecord(%list, %second);
%list = setRecord(%list, %first, %b);
%list = setRecord(%list, %second, %a);
return %list;
}
I think it worked last time I tested it. It could easily be changed to work with other types as well. However, it would be troublesome, but not impossible, to make it work with "arrays".
%list = 3 NL 2 NL 1;
%list = QuickSortRecord(%list, getMax, 0, 3);
Show Posts