UE3:Insertion Sort Macro

Below is a macro that allows you to quickly implement the sorting of a dynamic array. The sorting is performed within the scope of the function where it is used. This reduces overhead created by function calling.

/**
 * Inline sorting algorithm, based on the Insertion Sort on the UnrealWiki
 * http://wiki.beyondunreal.com/Legacy:Insertion_Sort
 * 
 * Usage: include this include file in a class where you want to use it
 * using `include(sorter.uci)
 * When in a function where you want to perform sorting add `sort_decl();
 * right after the function declaration. Then at the place where you want
 * to sort a dynamic array use `sort(MyArray);
 * 
 * For example:
 * function test(array<int> myArray)
 * {
 *  `sort_decl();
 *  local int foo;
 *  `sort(myArray);   
 * }  
 *   
 * This sorting mechanism works for all types for which there is a > and
 * == operator. This is the case for most primitive types in the 
 * UnrealEngine.  For other types you need to declare the > and == 
 * operator yourself.
 * 
 * You are free to use this software as you like, as long as you don't
 * claim owner or authorship.              
 *
 * Last update: 2009-09-16 19:20 UTC
 */ 
 
`define sort_decl_m(tag) \
    local int __InsertIndex`{tag}, __RemovedIndex`{tag}, __High`{tag}, __Closest`{tag};
 
`define sort_m(array,tag) \
    for (__RemovedIndex`{tag} = 1; __RemovedIndex`{tag} < `{array}.length; ++__RemovedIndex`{tag}) { \
        if ( `{array}[__RemovedIndex`{tag} - 1] > `{array}[__RemovedIndex`{tag}] ) { \
            __InsertIndex`{tag} = 0;\
            __High`{tag} = __RemovedIndex`{tag} - 1; \
            while (__InsertIndex`{tag} <= __High`{tag}) { \
                __Closest`{tag} = (__InsertIndex`{tag} + __High`{tag}) / 2; \
                if ( `{array}[__Closest`{tag}] == `{array}[__RemovedIndex`{tag}] ) { \
                    __InsertIndex`{tag} = __Closest`{tag}; \
                    break; \
                } \
                if ( `{array}[__Closest`{tag}] > `{array}[__RemovedIndex`{tag}] ) { \
                    __High`{tag} = __Closest`{tag} - 1; \
                } \
                else if ( `{array}[__RemovedIndex`{tag}] > `{array}[__Closest`{tag}] ) { \
                    __InsertIndex`{tag} = __Closest`{tag} + 1; \
                } \
                else { \
                    `warn("There is a bug in your compare algorithm. !(A > B || B > A) should mean A == B");\
                    break;\
                } \
            } \
            if ( __InsertIndex`{tag} < __RemovedIndex`{tag} && `{array}[__RemovedIndex`{tag}] > `{array}[__InsertIndex`{tag}] ) { \
                ++__InsertIndex`{tag}; \
            } \
        } \
        else { \
            __InsertIndex`{tag} = __RemovedIndex`{tag}; \
        } \
        if ( __RemovedIndex`{tag} != __InsertIndex`{tag} ) { \
            `{array}.Insert(__InsertIndex`{tag}, 1); \
            `{array}[__InsertIndex`{tag}] = `{array}[__RemovedIndex`{tag} + 1]; \
            `{array}.Remove(__RemovedIndex`{tag} + 1, 1); \
        } \
    }
 
// Short hand notation when you only need 1 sorter in a function.
`define sort_decl `sort_decl_m(_)
`define sort(array) `sort_m(`array, _)

Save the above code as sorter.uci.

Example

`include(sorter.uci)
 
function intSorter()
{
    `sort_decl();
    local int i;
    local array<int> data;
    data.length = 10;
    data[0] = 4; data[1] = 7; data[2] = 10; data[3] = 3; data[4] = 5; data[5] = 9; data[6] = 2; data[7] = 8; data[8] = 1; data[9] = 6;
 
    `log("Before:");
    for (i = 0; i < data.length; ++i)
    {
        `log(data[i]);
    }
 
    `sort(data);
 
    `log("After:");
    for (i = 0; i < data.length; ++i)
    {
        `log(data[i]);
    }
}

Custom type notice

You can sort any array with this macro, as long as the greater than (>), and equals (==) operators have been defined for that type. When you define these operators make sure the following constraint is valid: !(A > B || B > A) then A == B

In layman's terms: when A is not larger than B, and B is not larger than A, then A must be equal to B.

If this constraint does not uphold for your operators that the sorting algorithm will not function properly. And you will see warning in the log during sorting.

Related Topics

• Legacy:Insertion_Sort