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);   
 * }
 * 
 * Alternatively you can use the sorting with an different compare 
 * operator using: `sort_op(Myarray, <)
 * The second argument is the operator to use.   
 *   
 * This sorting mechanism works for all types for which there is a > 
 * operator. This is the case for most primitive types in the
 * UnrealEngine. For other types you need to declare the > 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-17 20:34:29              
 */ 

`define sort_decl_m(tag) \
    local int __InsertIndex`{tag}, __RemovedIndex`{tag}, __High`{tag}, __Closest`{tag};

`define sort_m_op(array,tag,operator) \
    for (__RemovedIndex`{tag} = 1; __RemovedIndex`{tag} < `{array}.length; ++__RemovedIndex`{tag}) { \
        if ( `{array}[__RemovedIndex`{tag} - 1] `operator `{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}] `operator `{array}[__RemovedIndex`{tag}] ) { \
                    __High`{tag} = __Closest`{tag} - 1; \
                } \
                else if ( `{array}[__RemovedIndex`{tag}] `operator `{array}[__Closest`{tag}] ) { \
                    __InsertIndex`{tag} = __Closest`{tag} + 1; \
                } \
                else { \
                    __InsertIndex`{tag} = __Closest`{tag}; \
                    break; \
                } \
            } \
            if ( __InsertIndex`{tag} < __RemovedIndex`{tag} && `{array}[__RemovedIndex`{tag}] `operator `{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); \
        } \
    }

`define sort_m(array,tag) `sort_m_op(`array, `tag, >)

// These are the standard macros you would use, only use the "_m" macros
// in case of naming conflicts with the variables

// Declare the variables used for the sorting
`define sort_decl `sort_decl_m(_)

// Sort the given array
`define sort(array) `sort_m_op(`array, _, >)

// Sort using an alternative operator, for example use `sort_op(array,>)
// to perform reverse order sorting.
`define sort_op(array,op) `sort_m_op(`array, _, `op)

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

    `sort_op(data, <);
    
    `log("Reversed:");
    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 (>) operator have been defined for that type. Or when you use the sort_op(Array,Operator) macro, the specified operator.

You can use the following template for implementing the operator for the type you want to sort:

static final operator(24) bool > ( MyCustomType A, MyCustomType B )
{
    // TODO: implement
}

It's best to define the operator as static and final, this improves the execution speed.

Related Topics

• Legacy:Insertion_Sort