Legacy:QuickSort - Unreal Wiki

# Legacy:QuickSort

### From Unreal Wiki, The Unreal Engine Documentation Site

QuickSort is a useful, very fast, algorithm that is used for sorting arrays. For more information, see Wikipedia:Quicksort.

## For this to work

- The array to be sorted is called MyArray.
- The values High and Low represent the range that is to be sorted.

## Algorithm

1. Split the array in half, set x to be the value of the partition element.
2. Starting from the bottom, increment the Low (i) value until you reach a value that is equal to or higher than the partition element (x).
3. Starting from the top, decrement the High (j) value until you reach a value that is lower than or equal to the partition element (x).
4. If the element at array index i is less than or equal to the element at array index j, swap them.
5. Goto 2, until i is larger than j, where you proceed.
6. QuickSort calls itself twice recursivly to sort the upper/lower parts of the array.

## Code

    Function SortArray(Int Low, Int High) //Sortage
    {
    //  low is the lower index, high is the upper index
    //  of the region of array a that is to be sorted

        local Int i,j;
        local String x;

        i = Low;
        j = High;
        x = MyArray[(Low+High)/2];

        //  partition
        do
            {
            while (MyArray[i] < x)
                i += 1;
            while (MyArray[j] > x)
                j -= 1;
            if (i <= j)
                {
                SwapArray(i,j);
                i += 1;
                j -= 1;
                }
            } until (i > j);

        //  recursion
        if (low < j)
            SortArray(low, j);
        if (i < high)
            SortArray(i, high);
    }

    Function SwapArray(Int EL1, Int EL2) //Function to swap two elements in an array
    {
        Local String Temp;

        Temp = MyArray[EL1];
        MyArray[EL1] = MyArray[EL2];
        MyArray[EL2] = Temp;
    }

Wormbo: Function calls are slow, so it might be a good idea to include the code for swapping the array elements in the main function.

Foxpaw: I've done that in my implementations, but perhaps it's easier to understand when it's modular in this fashion.

## Tips

The above functions assume you are sorting a string array, but you can easily adapt it for any type of values. When sorting struct or object arrays you will probably want to overload the < and > operators.

Here's an example that could be used e.g. for arrays of weapons:

    //=============================================================================
    // operator >
    // operator <
    //
    // Greater than and less then operators for Inventory objects.
    //=============================================================================

    static final operator(24) bool > (Inventory A, Inventory B)
    {
      if ( A == None ) {
        return B != None;
      }
      else {
        if ( B == None )
          return false;
        else {
          if ( A.InventoryGroup != B.InventoryGroup )
            return A.InventoryGroup > B.InventoryGroup;
          else
            return A.GroupOffset > B.GroupOffset;
        }
      }
    }

    static final operator(24) bool < (Inventory A, Inventory B)
    {
      return B > A;
    }

## Related Topics

- Open Source
- Insertion Sort

Category: Legacy Algorithm

##### Views

- Legacy
- Discussion
- Current revision

##### Search