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]);
    }
}

Related Topics

• Legacy:Insertion_Sort