XSIUtils.QuickSort

Description

Performs an in-place QuickSort of an array (which can be multi-dimensional). The sort is performed on the first element of each dimension. If the first elements are equal, then the second elements are compared, and so on.

There are several types of sorting algorithms, such as BubbleSort, QuickSort, Insertion, Shaker, and Selection. The QuickSort algorithm is very good at sorting large amounts of data efficiently. It basically uses a divide-and-conquer approach.

Note: This method invokes the built-in JScript sort method when the Array argument is a Jscript array. The JScript sort method uses a case-sensitive text-based ordering, which is not likely to be the intended result when sorting numeric data. A workaround is demonstrated in the examples below.

Scripting Syntax

XSIUtils.QuickSort( Array );

Parameters

Parameter Type Description
Array Array The array to sort.

Examples

1. VBScript Example

'
' This example demonstrates how to sort an array with the QuickSort method. 
'
Dim aValues
aValues = array(8,1,9,4,6)
XSIUtils.QuickSort aValues
for each item in aValues
        Application.LogMessage item 
next
' Expected result:
'INFO : "1"
'INFO : "4"
'INFO : "6"
'INFO : "8"
'INFO : "9"

2. Python Example

#
# This example demonstrates how to sort an array with the QuickSort method. 
#
aValues = [8,1,9,4,6]
aValues = XSIUtils.QuickSort(aValues)
for item in aValues:
        Application.LogMessage( '%(item)d'%vars() )
# Expected result:
#INFO : "1"
#INFO : "4"
#INFO : "6"
#INFO : "8"
#INFO : "9"

3. VBScript Example

'VBScript example : sort of a 2 dimension array
Dim TestArray()
ReDim TestArray(4, 4)
TestArray(0, 0) = -1.9
TestArray(1, 0) = 8
TestArray(2,0) = 4
TestArray(3,0) = 543
TestArray(4,0) = 0
TestArray(0, 1) = 3.2
TestArray(1, 1) = 5
TestArray(2,1) = -100
TestArray(3,1) = 99
TestArray(4,1) = 2
TestArray(0, 2) = 10.3
TestArray(1, 2) = 7
TestArray(2,2) = 6
TestArray(3,2) = 5
TestArray(4,2) = 4
TestArray(0, 3) = 3.2
TestArray(1, 3) = 9
TestArray(2,3) = 2
TestArray(3,3) = 3
TestArray(4,3) = 4
TestArray(0, 4) = -5.4
TestArray(1, 4) = 2
TestArray(2,4) = 1000
TestArray(3,4) = 500
TestArray(4,4) = 2000
Application.LogMessage "Array before sort : "
Application.LogMessage TestArray(0, 0) & " " & TestArray(1, 0) & " " & TestArray(2, 0) & " " & TestArray(3, 0) & " " & TestArray(4, 0)
Application.LogMessage TestArray(0, 1) & " " & TestArray(1, 1) & " " & TestArray(2, 1) & " " & TestArray(3, 1) & " " & TestArray(4, 1)
Application.LogMessage TestArray(0, 2) & " " & TestArray(1, 2) & " " & TestArray(2, 2) & " " & TestArray(3, 2) & " " & TestArray(4, 2)
Application.LogMessage TestArray(0, 3) & " " & TestArray(1, 3) & " " & TestArray(2, 3) & " " & TestArray(3, 3) & " " & TestArray(4, 3)
Application.LogMessage TestArray(0, 4) & " " & TestArray(1, 4) & " " & TestArray(2, 4) & " " & TestArray(3, 4) & " " & TestArray(4, 4)
XSIUtils.QuickSort TestArray
Application.LogMessage "Array after sort : "
Application.LogMessage TestArray(0, 0) & " " & TestArray(1, 0) & " " & TestArray(2, 0) & " " & TestArray(3, 0) & " " & TestArray(4, 0)
Application.LogMessage TestArray(0, 1) & " " & TestArray(1, 1) & " " & TestArray(2, 1) & " " & TestArray(3, 1) & " " & TestArray(4, 1)
Application.LogMessage TestArray(0, 2) & " " & TestArray(1, 2) & " " & TestArray(2, 2) & " " & TestArray(3, 2) & " " & TestArray(4, 2)
Application.LogMessage TestArray(0, 3) & " " & TestArray(1, 3) & " " & TestArray(2, 3) & " " & TestArray(3, 3) & " " & TestArray(4, 3)
Application.LogMessage TestArray(0, 4) & " " & TestArray(1, 4) & " " & TestArray(2, 4) & " " & TestArray(3, 4) & " " & TestArray(4, 4)

4. JScript Example

// This example demonstrates using XSIUtils.Sort
// with a JScript error.
a = new Array( "C", "a", "Check", "Z", "zed" ) ;
logmessage("before: a=[" + a + "]");
// This is identical to calling a.sort(); 
XSIUtils.QuickSort(a);
logmessage("after: a=[" + a + "]");
//Expected output (notice that the sort has
//been performed in a case-sensitive fashion)
//INFO : after: a=[C,Check,Z,a,zed]

5. JScript Example

// This example shows how better sort results
// can be achieved by using the built-in JScript 
// array sorting algorithm.
//
//----------------------
// MySortFunction is a function provided to the
// sort method to implement the comparison function.
//
// As documented in the JScript documentation this 
// method must return:
// -A negative value if the first argument passed is less than the second argument. 
// -Zero if the two arguments are equivalent. 
// -A positive value if the first argument is greater than the second argument
//
// In this basic example the sort function can sort strings
// or numbers but does not expect a mix of both types and
// does not sort other types of data.
//----------------------
function MySortFunction( a, b )
{
        if ( typeof( a ) == "string" )
        {               
                aLower = a.toLowerCase() ;
                bLower = b.toLowerCase() ;
                if ( aLower < bLower )
                {
                        return -1 ;
                }
                else if ( bLower < aLower )
                {
                        return 1 ;
                }
                return 0 ;
        }
        else if ( typeof( a ) == "number" )
        {       
                return a - b ;
        }
        else
        {
                throw( new Error( 0, 
                                "This function can only sort numbers and strings" ) ) ;
        }
}
// Demonstrate with strings
testArray = new Array( "C", "a", "Check", "Z", "zed" ) ;
testArray.sort( MySortFunction ) ;
logmessage("after: testArray=[" + testArray + "]");
//Expected output
//INFO : after: testArray=[a,C,Check,Z,zed]
// Demonstrate with numbers
testArray = new Array( 0.3, -1.9, 2, 1e10, 0 ) ;
testArray.sort( MySortFunction ) ;
logmessage("after: testArray=[" + testArray + "]");
//Expected output
//INFO : after: testArray=[-1.9,0,0.3,2,10000000000]