Unreal Archive / Wikis / Unreal Wiki / Legacy:QuickSort

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

1 For this to work
2 Algorithm
3 Code
4 Tips
5 Related Topics

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

Split the array in half, set x to be the value of the partition element.
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).
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).
If the element at array index i is less than or equal to the element at array index j, swap them.
Goto 2, until i is larger than j, where you proceed.
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;
}

Wikis / Unreal Wiki / Legacy:QuickSort

Contents

For this to work

Algorithm

Code

Tips

Related Topics

Page Categories

Page Information