Legacy:QuickSort

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

<uscript> 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;

} </uscript>

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:

<uscript> //============================================================================= // 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;

} </uscript>

Related Topics

• Open Source
• Insertion Sort