| Home Page | Recent Changes | Preferences

# QuickSort

QuickSort is a useful, very fast, algorithm that is used for sorting arrays. For more information, see 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 AZ1;
        Local String AZ2;

        AZ2 = MyArray[EL1];
        AZ1 = MyArray[EL2];

        MyArray[EL2] = AZ2;
        MyArray[EL1] = AZ1;
    }

## 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

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

Mapping Topics

Mapping Lessons

UnrealEd Interface

Questions&Answers

Scripting Topics

Scripting Lessons

Making Mods

Class Tree

Questions&Answers

Modeling Topics

Questions&Answers

Log In