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);   
* }  
*   
* 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 > operator yourself.
* 
* You are free to use this software as you like, as long as you don't
* claim owner or authorship.              
*/ 

`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; \
               } \
           } \
           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, _) </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]);
   }

} </uscript>

Related Topics

• Legacy:Insertion_Sort