| Home Page | Recent Changes | Preferences

QuickSort

QuickSort is a useful, very fast, algorithm that is used for sorting arrays. For more information, see Wikipedia logo 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


Category Algorithm

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

FAQs

Help Desk

Mapping Topics

Mapping Lessons

UnrealEd Interface

UnrealScript Topics

UnrealScript Lessons

Making Mods

Class Tree

Modeling Topics

Chongqing Page

Log In