SerraAvenger
Cuz I can
- Reaction score
- 234
The QuickSort Algorithm
requires:
- JassPack NewGen
- Jass Knowledge
This code sorts the ToSort array and the ParallelSort one at the same time.
It works quite fast, for the smaller subarrays it uses insert sort to keep the stack lower and for the bigger sorting it uses QSort with some sort of "median of two". Simply copy this in your map header, and then copy the array you want to sort in the ToSort array, run QSort on the fields you want to sort ( like from 2 to 700, use QSort( 2 , 700 ) ) and then copy the data back.
If anyone requests a demo map I'll add one, but I don't think that sorting would need demonstration : /
Hf with your faster sorting
Davey
EDIT: Uploaded Demo map. Simply open it with Grimoire running and enter -test XXXX , with XXXX being the integer on your choice. It will then fill the first XXXX fields of the ToSort array with random integers between 1 and XXXX, and then apply quicksort. After the sorting has finished, all the numbers will be shown in sorted order. After 740 it will most probably hit the op limiter.
Demo map and attached text file currently out of date! Please do not use.
requires:
- JassPack NewGen
- Jass Knowledge
This code sorts the ToSort array and the ParallelSort one at the same time.
It works quite fast, for the smaller subarrays it uses insert sort to keep the stack lower and for the bigger sorting it uses QSort with some sort of "median of two". Simply copy this in your map header, and then copy the array you want to sort in the ToSort array, run QSort on the fields you want to sort ( like from 2 to 700, use QSort( 2 , 700 ) ) and then copy the data back.
JASS:
//*********************************************************************
// The Quicksort Algorithm *
// - Median of two ; Insertsort for arrays of 4 and less- *
// Expected efficiency : O( n * log n ) *
// Worst case efficiency: O( n² ) *
//**********************************************************************************************************************
//* !!! All array members that will be sorted need to have a value! All Parallelsort fields need to have a value too! *
//* !!! The Tosort Variable needs to be of Type Integer! *
//* !!! To use it, write //! runtextmacro QSORT( the array to be sorted, the array to be parallely sorted, and the *
//* type of the array that is sorted parallely. Example: *
//* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *
// globals
// integer array HeroLevel
// unit array Heroes
// integer NumHeroes
// endglobals
//
// //! runtextmacro QSORT( HeroLevel , Heroes, unit )
//
// function DisplayMaxHeroLevel takes nothing returns nothing
// call QSortHeroLevel( 0 , NumHeroes )
// call DisplayTextToPlayer( GetLocalPlayer() , 0 , 0 , "|cffffcc00The highest-level Hero is " + GetUnitName( Heroes[ NumHeroes ] ) ) *
// endfunction
//
//* - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - *
//* So to make the array sortable, run the textmacro. Then to actually sort it, use *
//*
// call QSort[the array to be sorted]( lower sorting bound , upper sorting bound )
//*
//* Not difficult at all, is it? *
//* Only bad thing: You allways need a filled parallelsort for it, which needs to be different from the array to be *
//* sorted. Most probably you would've needed it anyway, but not allways. *
//**********************************************************************************************************************
//* Coded by Cpt.DaveyJones/SerraAvenger, invented by C. A. R. Hoare
library QuickSort
//! textmacro QSORT takes TOSORT , PARALLELSORT , PARALLELTYPE
function InsertSort$TOSORT$ takes integer lowerbound, integer upperbound returns nothing
local integer outerLoop = lowerbound + 1
local integer innerLoop
local integer key
local $PARALLELTYPE$ lock
loop
exitwhen outerLoop > upperbound
set innerLoop = outerLoop
set key = $TOSORT$ [ outerLoop ]
set lock = $PARALLELSORT$[ outerLoop ]
loop
exitwhen innerLoop <= lowerbound
exitwhen $TOSORT$ [ innerLoop - 1 ] < key
set $TOSORT$ [ innerLoop ] = $TOSORT$ [ innerLoop - 1 ]
set $PARALLELSORT$[ innerLoop ] = $PARALLELSORT$[ innerLoop - 1 ]
set innerLoop = innerLoop - 1
endloop
set $TOSORT$ [ innerLoop ] = key
set $PARALLELSORT$[ innerLoop ] = lock
set outerLoop = outerLoop + 1
endloop
//if not ("$PARALLELTYPE$" == "integer" or "$PARALLELTYPE$" == "real" ) then
// set lock = null
//endif
endfunction
function QSort$TOSORT$ takes integer lowerbound, integer upperbound returns nothing
local integer pivot = ( $TOSORT$[ lowerbound ] + $TOSORT$[ upperbound ] + $TOSORT$[ GetRandomInt( lowerbound, upperbound ) ] ) / 3
local integer leftIndicator = lowerbound
local integer rightIndicator = upperbound
local integer tempValue
local $PARALLELTYPE$ tempParallelValue
if upperbound - lowerbound > 8 then
loop
loop
exitwhen $TOSORT$[ rightIndicator ] < pivot
exitwhen rightIndicator == leftIndicator
set rightIndicator = rightIndicator - 1
endloop
loop
exitwhen $TOSORT$[ leftIndicator ] >= pivot
exitwhen leftIndicator == rightIndicator
set leftIndicator = leftIndicator + 1
endloop
exitwhen leftIndicator > rightIndicator
set tempValue = $TOSORT$[ rightIndicator ]
set $TOSORT$[ rightIndicator ] = $TOSORT$[ leftIndicator ]
set $TOSORT$[ leftIndicator ] = tempValue
set tempParallelValue = $PARALLELSORT$[ rightIndicator ]
set $PARALLELSORT$[ rightIndicator ] = $PARALLELSORT$[ leftIndicator ]
set $PARALLELSORT$[ leftIndicator ] = tempParallelValue
endloop
call QSort$TOSORT$( lowerbound , leftIndicator )
call QSort$TOSORT$( rightIndicator + 1 , upperbound )
else
call InsertSort$TOSORT$( lowerbound, upperbound )
endif
endfunction
//! endtextmacro
endlibraryIf anyone requests a demo map I'll add one, but I don't think that sorting would need demonstration : /
Hf with your faster sorting
Davey
EDIT: Uploaded Demo map. Simply open it with Grimoire running and enter -test XXXX , with XXXX being the integer on your choice. It will then fill the first XXXX fields of the ToSort array with random integers between 1 and XXXX, and then apply quicksort. After the sorting has finished, all the numbers will be shown in sorted order. After 740 it will most probably hit the op limiter.
Demo map and attached text file currently out of date! Please do not use.
