- Joined
- Mar 19, 2008
- Messages
- 3,140
Implementation of QuickSort and InsertionSort for sorting elements of type <T>. Designed in way which enables user to provide his own comparator.
Note: default comparator is defined only for integers and reals thus other types and especially complex comparisons (struct instances comparison) require user to implement compare method on the top of given struct. Library is fool-proof. No comparator? Script block won't even load.
Note: compare method much use following syntax:
Function should return integer value: 0, -1 or 1 depending on outcome.
Uses multiple modifications to improve efficiency when dealing with high amount of data. Recursion approach. Elements compared via less function.
To provide intuitive api and due to lack of pointers in jass I've decided to use Table as an array object. Since Array<T> and Vector<T> are child structs to Table, the .data() member allows to use sort in convenient way.
Special thanks to looking_for_help for helping me fix awkard issue with comparators.
Requires newest Table update.
Huge applause goes to Bribe for updating his amazing Table to better accommodate this resource.
Demo:
Note: default comparator is defined only for integers and reals thus other types and especially complex comparisons (struct instances comparison) require user to implement compare method on the top of given struct. Library is fool-proof. No comparator? Script block won't even load.
Note: compare method much use following syntax:
static method compare_<type> takes <type> a, <type> b returns integerFunction should return integer value: 0, -1 or 1 depending on outcome.
Uses multiple modifications to improve efficiency when dealing with high amount of data. Recursion approach. Elements compared via less function.
To provide intuitive api and due to lack of pointers in jass I've decided to use Table as an array object. Since Array<T> and Vector<T> are child structs to Table, the .data() member allows to use sort in convenient way.
Special thanks to looking_for_help for helping me fix awkard issue with comparators.
Requires newest Table update.
Huge applause goes to Bribe for updating his amazing Table to better accommodate this resource.
JASS:
/*****************************************************************************
*
* QuickSort v1.0.2.2
* by Bannar aka Spinnaker
*
* Sorts data of desired type using quick sort algorithm.
*
******************************************************************************
*
* Requirements:
* Table by Bribe
* hiveworkshop.com/forums/jass-resources-412/snippet-new-table-188084/
*
* Table requirement is needed due to lack of pointers within jass. Implementing intuitive
* api requires object that can represent an array and which can be passed through
* functions while changes made during procedure are actually saved within such object
*
******************************************************************************
*
* Implementation:
*
* macro DEFINE_QSORT takes NAME, TYPE, OBJECT, COMPARATOR
*
* NAME - sets name for quick sort type struct
* TYPE - type of values to sort
* OBJECT - boolean, tells whether array stores struct objects or not
* COMPARATOR - optional argument, however, if compare method is non existant
* sort code won't be implemented
*
******************************************************************************
*
* struct API:
*
* static constant string valueType
*
* static method isort takes Table input, integer lo, integer hi returns nothing
* performs insertion sort procedue on object input with interators range lo to hi
*
* static method qsort takes Table input, integer lo, integer hi returns nothing
* performs quick sort procedue on object input with interators range lo to hi
*
* static method isortSimple takes Table input, integer size returns nothing
* simple adaptation of isort; iterator lo is set to 0
*
* static method qsortSimple takes Table input, integer size returns nothing
* simple adaptation of qsort; iterator lo is set to 0
*
******************************************************************************/
library QuickSortTemplate requires Table
globals
/**
defines how small table size within given iteration
has to be before insertion sort is performed
*/
constant integer QUICK_SORT_CUTOFF = 8
endglobals
//! textmacro_once DEFINE_QSORT takes NAME, TYPE, OBJECT, COMPARATOR
struct $NAME$ extends array
readonly static string valueType = "$TYPE$"
implement optional $COMPARATOR$
static if not thistype.compare.exists then
static if LIBRARY_$TYPE$DefaultComparator then
implement optional $TYPE$DefaultComparator
endif
endif
static if thistype.compare.exists then
private static method Set takes Table table, integer index, $TYPE$ value returns nothing
static if $OBJECT$ then
set table[index] = value
else
set table.$TYPE$[index] = value
endif
endmethod
private static method get takes Table table, integer index returns $TYPE$
static if $OBJECT$ then
return table[index]
else
return table.$TYPE$[index]
endif
endmethod
private static method less takes $TYPE$ a, $TYPE$ b returns boolean
return ( thistype.compare(a, b) < 0 )
endmethod
private static method equal takes $TYPE$ a, $TYPE$ b returns boolean
return ( thistype.compare(a, b) == 0 )
endmethod
private static method swapInput takes Table input, integer a, integer b returns nothing
local $TYPE$ tmp = get(input, a)
call Set(input, a, get(input, b))
call Set(input, b, tmp)
endmethod
private static method median3 takes Table input, integer i, integer j, integer k returns integer
if ( less( get(input, i), get(input, j) ) ) then
if ( less( get(input, j), get(input, k) ) ) then
return j
else
if ( less( get(input, i), get(input, k) ) ) then
return k
else
return i
endif
endif
else
if ( less( get(input, k), get(input, j) ) ) then
return j
else
if ( less( get(input, k), get(input, i) ) ) then
return k
else
return i
endif
endif
endif
endmethod
private static method insertionSort takes Table input, integer lo, integer hi returns nothing
local integer i = lo
local integer j
loop
exitwhen ( i > hi )
set j = i
loop
exitwhen j <= lo or not less( get(input, j), get(input, j-1) )
call swapInput(input, j, j-1)
set j = j - 1
endloop
set i = i + 1
endloop
endmethod
private static method quickSort takes Table input, integer lo, integer hi returns nothing
local integer lenN = hi - lo + 1
local integer median
local integer eps
local integer mid
local integer mFirst
local integer mMid
local integer mLast
local integer ninther
local $TYPE$ value
// iterators
local integer iterI = lo
local integer iterP = lo
local integer iterJ = hi + 1
local integer iterQ = hi + 1
local integer k
// less than cutoff? use insertion sort instead
if ( lenN <= QUICK_SORT_CUTOFF ) then
call insertionSort(input, lo, hi)
return
// use just median3 for small array
elseif ( lenN <= 40 ) then
set median = median3(input, lo, lo + lenN / 2, hi)
call swapInput(input, median, lo)
// Tukey ninther for finding partitioning element
else
set eps = lenN / 8
set mid = lo + lenN / 2
set mFirst = median3(input, lo, lo + eps, lo + eps + eps)
set mMid = median3(input, mid - eps, mid, mid + eps)
set mLast = median3(input, hi - eps - eps, hi - eps, hi)
set ninther = median3(input, mFirst, mMid, mLast)
call swapInput(input, ninther, lo)
endif
// sort using 3-way partitioning
set value = get(input, lo)
loop
loop
set iterI = iterI + 1
exitwhen not less( get(input, iterI), value )
if ( iterI == hi ) then
exitwhen true
endif
endloop
loop
set iterJ = iterJ - 1
exitwhen not less( value, get(input, iterJ) )
if ( iterJ == lo ) then
exitwhen true
endif
endloop
// cross pointers
if ( iterI == iterJ and equal( get(input, iterI), value ) ) then
set iterP = iterP + 1
call swapInput(input, iterP, iterI)
endif
if ( iterI >= iterJ ) then
exitwhen true
endif
call swapInput(input, iterI, iterJ)
if ( equal( get(input, iterI), value ) ) then
set iterP = iterP + 1
call swapInput(input, iterP, iterI)
endif
if ( equal( get(input, iterJ), value ) ) then
set iterQ = iterQ - 1
call swapInput(input, iterQ, iterJ)
endif
exitwhen false
endloop
set iterI = iterJ + 1
set k = lo
loop
exitwhen k > iterP
call swapInput(input, k, iterJ)
set iterJ = iterJ - 1
set k = k + 1
endloop
set k = hi
loop
exitwhen k < iterQ
call swapInput(input, k, iterI)
set iterI = iterI + 1
set k = k - 1
endloop
call quickSort(input, lo, iterJ)
call quickSort(input, iterI, hi)
endmethod
static method isort takes Table input, integer lo, integer hi returns nothing
call insertionSort(input, lo, hi)
endmethod
static method qsort takes Table input, integer lo, integer hi returns nothing
call quickSort(input, lo, hi)
endmethod
static method isortSimple takes Table input, integer size returns nothing
call insertionSort(input, 0, size-1)
endmethod
static method qsortSimple takes Table input, integer size returns nothing
call quickSort(input, 0, size-1)
endmethod
endif
endstruct
//! endtextmacro
endlibrary
// Default integer & real comparators
//! textmacro_once DEFINE_DEFAULT_COMPARATOR takes TYPE
library_once $TYPE$DefaultComparator
module $TYPE$DefaultComparator
static method compare takes $TYPE$ a, $TYPE$ b returns integer
if ( a < b ) then
return -1
elseif ( a == b ) then
return 0
else // ( a > b )
return 1
endif
endmethod
endmodule
endlibrary
//! endtextmacro
//! runtextmacro DEFINE_DEFAULT_COMPARATOR("integer")
//! runtextmacro DEFINE_DEFAULT_COMPARATOR("real")
JASS:
//! runtextmacro DEFINE_ARRAY("Array", "integer", "9", "0", "false")
//! runtextmacro DEFINE_QSORT("IntegerSort", "integer", "false", "")
struct qsort_struct extends array
static method print takes Table tb, integer size, string prefix returns nothing
local integer i = size
local string s = ""
loop
exitwhen 0 == i
set i = i-1
set s = I2S(tb[i]) + ", " + s
endloop
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, prefix + s)
set s = null
endmethod
static method qsort_test takes nothing returns nothing
local integer max = 9
local integer i
local string s
local Array arr = Array.create()
set arr[0] = 55
set arr[1] = 3
set arr[2] = 88
set arr[3] = 9
set arr[4] = -10
set arr[5] = 1
set arr[6] = 17
set arr[7] = -1
set arr[8] = 26
call print(arr.data(), arr.size(), "Before: ")
call IntegerSort.qsort(arr.data(), 0, 8)
call print(arr.data(), arr.size(), "After: ")
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(), 2, false, function thistype.qsort_test)
endmethod
endstruct
module CompareStrings
static method compare takes string a, string b returns integer
if ( a == b ) then
return 0
elseif ( StringLength(a) < StringLength(b) ) then
return -1
else // ( a > b )
return 1
endif
endmethod
endmodule
//! runtextmacro DEFINE_QSORT("StringSort", "string", "false", "CompareStrings")
Last edited:
