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.

<uscript> /**

* 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) </uscript>

Save the above code as sorter.uci.

Example

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

} </uscript>

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: <uscript> static final operator(24) bool > ( MyCustomType A, MyCustomType B ) {

   // TODO: implement

} </uscript> It's best to define the operator as static and final, this improves the execution speed.

Related Topics

• Legacy:Insertion_Sort