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