Many times I've wondered... how much there is to know.
- Jimmy Page and Robert Plant
aztec.util.QuickSort
public class QuickSort<T>
Base
QuickSort<>
The QuickSort class is a "template" based class that takes an array reference to be sorted. The entire array or a subset of the array can be sorted. The array can contain primitive objects, primitive references, and normal class references. The array cannot contain method references. No error is given in that case, and the sort operation will simply not do anything. The array will remain unchanged.
The QuickSort class provides at least three different ways of performing the sort operation.
1. Use the QuickSort class with no sort handler.
.
- Instantiate the QuickSort class with the class and the actual array that is to be sorted (new<QuickSort<MyClass>(MyArray)>).
- Call the Sort() method. Since no compare handler is specified, the system will perform an automatic comparison of items to perform the sort (see below).
2. Use the QuickSort class and manually define a sort handler.
- Instantiate the QuickSort class with the class that is to be sorted (new<QuickSort<MyClass>(MyArray)>).
- Manually set the comparison handler method using SetCompareHandler(). This method will be called by the system to compare two items and return a result.
- Call the Sort() method. It will repeatedly call the method specified by SetCompareHandler() until the array is sorted.
3. Use a class derived from QuickSort<>.
- Instantiate a class derived from QuickSort (class MyClassSort from<QuickSort<MyClass>>), (new<MyClassSort(MyArray)>).
- Override the virtual Compare() method in the derived class and implement the code to compare two items.
- Call the Sort() method. It will repeatedly call the Compare method in the derived class until the array is sorted.
The comparison method, either manual or automatic, is responsible for comparing two items from the array and determining whether one is less than, equal to, or greater than the other item. The comparison method knows nothing about the internal sorting algorithm, and does not typically know which two items in the array are being compared. It does not need to. It simply provides the script/application business logic to compare two data items of a particular class. Likewise, the internal sorting algorithm does not need to know anything about the business logic driving the comparison. It uses the "black box" handler method as a tool to efficiently sort the array, without knowing anything about the contents.
The manual comparison logic mentioned in methods 2 and 3 above also have the benefit of an "ExtraObject", which is a script/application specific object that can be used inside the comparison method if needed. It is passed into the Sort() method, and the internal sorting algorithm passes it into the comparison method each time it is called.
Using the automatic sort operation specified in step 1, the following rules are used to determine how the item comparison is performed, based on the data type of the array.
- If primitive objects, the comparison will be identical to the logic used by the Aztec Compiler and Virtual Machine for handling the '<', '==' and '>' operators.
- If primitive references, the actual primitive objects that are being referenced are compared using the same rules for a primitive object array.
- If normal class based objects, a standard integer comparison will be performed using the embedded ObjectId values.
- For any type of reference comparison, a "null" value is handled specially. A "null" value will always be treated as "less than" a "non-null" value, regardless of data type. If both items are null, they are considered equal.
There is no ascending/descending flag in the QuickSort<> class interface. The primary intent of this class is for the script/application to control the comparison logic using methods 2 and 3 described above. The automatic sorting in method 1 is provided mainly for completeness, and it would typically be easier to use the Array.Sort() method to sort the array using the same automatic sorting algorithm that is provided here. The Array.Sort() method does provide an ascending/descending flag. The script/application controlled logic used in methods 2 and 3 above can determine itself based on its own internal business logic whether the array should be sorted in an ascending or descending order, and it can handle the comparison result accordingly.
The creation of a specific implementation of this template class also results in the creation of a method handler data type used for the comparison method, named SortHandler<>, as shown below.
The SortHandler<T> data type represents a method reference specific to a handler for a QuickSort<> comparison method. SortHandler<T> is defined as follows:
public type<int method<T,T,Base>> SortHandler<T>
Given this definition, the method handler for sort comparison must be defined with the following signature (name can be anything). T is a placeholder for the actual class that was used in that particular implementation of the template.
public method<int> MySortCompareMethod(T Object1, T Object2, Base ExtraObject) { }.
QuickSort<> Methods
| QuickSort() |
Constructor for the QuickSort<> class |
| Sort() |
Initiates the sorting process for the specified array |
| Compare() |
Virtual method to compare two items and return the result |
| SetCompareHandler() |
Sets the method to be used as a comparison handler during the sort operation |
Derived Classes
None
See Also
Class Hierarchy, Array Methods
QuickSort()
public method QuickSort(T[ ] SortArray)
Parameters
SortArray
One dimensional array to be sorted, with data type specified in creation of the template class
Return Value
None
Description
Constructor for the QuickSort<> class. The array containing the data to be sorted is passed in and must not be null.
QuickSort<> Class
Sort()
public virtual method Sort(Base ExtraObject = null, int LowLimit = 1, int HighLimit = 0)
Parameters
ExtraObject
Script/application specific object to be passed into the comparison method (default is null)
LowLimit
Low limit of the array index to be used in sort operation (one based, default is 1)
HighLimit
High limit of the array index to be used in sort operation (one based, default is 0, which means no upper limit)
Return Value
None
Description
This method performs the sort operation using the array passed into the constructor. The internal sort algorithm will repeatedly call a compare handler, comparing two items at a time, until the entire array (or subset) is sorted. The compare handler is either an internal method, a user specified method, or an override of the Compare() method. Refer to the discussion at the top of this page for more details.
A subset of the array can be sorted, leaving all data outside of the specified sort range intact and unchanged. Both limits are one based array indices to specify how much of the array to sort. If the high limit of the array is greater than zero, that will be the highest index of the array to be sorted. If the high limit is zero (default), there is no limit on the upper end, so the sort operation will go from the low limit to the end of the array.
QuickSort<> Class
Compare()
public method<int> unique virtual Compare(T Object1, T Object2, Base ExtraObject)
Parameters
Object1
Reference to first object to be compared
Object2
Reference to second object to be compared
ExtraObject
Reference to script/application specific object passed into constructor
Return Value
Result of the comparison: -1, 0 or 1
Description
This method compares the two items passed into the method and returns the result of the comparison. If Item1 is less then Item2, it returns -1. If they are equal, it returns 0, and if Item1 is greater than Item2, it returns 1.
This is the default implementation of the comparison handler, and the logic contained here will only be used if the user has not registed a comparison handler (SetCompareHandler()) and the user has not overridden the Compare method in a derived class. Refer to the description at the top of this page for default comparison logic.
QuickSort<> Class
SetCompareHandler()
public method SetCompareHandler(SortHandler<T> ComparisonMethod)
Parameters
ComparisonMethod
Method reference for the comparison method
Return Value
None
Description
This method sets a script/application specific method to perform the comparison for the sorting process. When the Sort() method is called, this sort handler method will then be called repeatedly in order to compare two items. This handler method does not need to know anything about the overall sorting algorithm. This method simply needs to perform a comparison between two of the items that are contained in the array and return the result. The result of the comparison is used by the internal sorting algorithm to determine whether more comparisons are needed or the entire array (or subset of the array) is sorted.
As described at the top of this page, the comparison method must conform to the following syntax (name is arbitrary).
public method<int> MySortCompareMethod(T Object1, T Object2, Base ExtraObject) { }
QuickSort<> Class
