- Joined
- Sep 6, 2013
- Messages
- 6,742
Normal sorting only sorts values from low to high or vice versa.
With index sorting you may attach your struct instance as index for example.
Normal sorting
Index sorting
Sorters hate that trick
With index sorting you may attach your struct instance as index for example.
Normal sorting
JASS:
library QuickSort
/*
Allows to sort an array of integer/real.
Complexity:
Best: O(n*log (n))
Average: O(n log n) .
Worst: O(n^2)
// For bigger unsorted arrays it gets unlikely to get the worst case.
// In tests it could sort arrays with size of ~650 until OP limit was hit.
Usage
¯¯¯¯¯¯¯
*/
//! novjass
// Fill this array:
real array QuickSortValue[]
// Ascending:
boolean QuickSortAscending
// just set it to true or false
// Start:
function QuickSort takes integer left, integer right returns nothing
// left is index where it starts
// right is index where it ends
//==============================================================//
//! endnovjass
globals
real array QuickSortValue
integer array QuickSortIndix
boolean QuickSortAscending = true
endglobals
/*
Get median of three values.
if (i < j)then
if(j<k) then
return j
elseif (k<pivot) then
return = k
else
return i
endif
elseif (k<j) then
return j
elseif (k<i) then
return k
else
return i
endif
*/
private function Partition takes integer left, integer right returns integer
local real pivot = QuickSortValue[left]
local integer l = left
local integer r = right
local real temp
loop
exitwhen l > r
if (QuickSortAscending and QuickSortValue[l] > pivot) or (not QuickSortAscending and QuickSortValue[l] < pivot) then
set temp = QuickSortValue[l]
set QuickSortValue[l] = QuickSortValue[r]
set QuickSortValue[r] = temp
set r = r - 1
else
set l = l + 1
endif
endloop
set temp = QuickSortValue[left]
set QuickSortValue[left] = QuickSortValue[r]
set QuickSortValue[r] = temp
return r
endfunction
function QuickSort takes integer left, integer right returns nothing
local integer i
if (left < right) then
set i = Partition(left, right)
call QuickSort(left, i - 1)
call QuickSort(i + 1, right)
endif
endfunction
endlibraryIndex sorting
JASS:
library QuickSort
/*
Allows to sort an array of integer/real.
Binds an extra integer (index)
to the filled value to allow keeping track of it.
Complexity:
Best: O(n*log (n))
Average: O(n log n) .
Worst: O(n^2)
// For bigger unsorted arrays it gets unlikely to get the worst case.
// In tests it could sort arrays with size of ~650 until OP limit was hit.
Usage
¯¯¯¯¯¯¯
*/
//! novjass
// Fill these arrays:
real array QuickSortValue[]
integer array QuickSortIndex[] // Requierement, not optional.
// Ascending:
boolean QuickSortAscending
// just set it to true or false
// Start:
function QuickSort takes integer left, integer right returns nothing
// left is index where it starts
// right is index where it ends
//==============================================================//
//! endnovjass
globals
real array QuickSortValue
integer array QuickSortIndex
boolean QuickSortAscending = true
endglobals
/*
Get median of three values.
if (i < j)then
if(j<k) then
return j
elseif (k<pivot) then
return = k
else
return i
endif
elseif (k<j) then
return j
elseif (k<i) then
return k
else
return i
endif
*/
private function Partition takes integer left, integer right returns integer
local real pivot = QuickSortValue[left]
local integer l = left
local integer r = right
local real tempR
local integer tempI
loop
exitwhen l > r
if (QuickSortAscending and QuickSortValue[l] > pivot) or (not QuickSortAscending and QuickSortValue[l] < pivot) then
set tempR = QuickSortValue[l]
set QuickSortValue[l] = QuickSortValue[r]
set QuickSortValue[r] = tempR
set tempI = QuickSortIndex[l]
set QuickSortIndex[l] = QuickSortIndex[r]
set QuickSortIndex[r] = tempI
set r = r - 1
else
set l = l + 1
endif
endloop
set tempR = QuickSortValue[left]
set QuickSortValue[left] = QuickSortValue[r]
set QuickSortValue[r] = tempR
set tempI = QuickSortIndex[left]
set QuickSortIndex[left] = QuickSortIndex[r]
set QuickSortIndex[r] = tempI
return r
endfunction
function QuickSort takes integer left, integer right returns nothing
local integer i
if (left < right) then
set i = Partition(left, right)
call QuickSort(left, i - 1)
call QuickSort(i + 1, right)
endif
endfunction
endlibrary
JASS:
scope QSortDemoOne initializer Init
private function print takes integer i, integer j returns nothing
loop
exitwhen i > j
call BJDebugMsg(R2S(QuickSortValue[i]))
set i = i + 1
endloop
endfunction
private function Init takes nothing returns nothing
set QuickSortValue[0] = 5.222
set QuickSortValue[1] = 5.111
set QuickSortValue[2] = 5.222
set QuickSortValue[3] = 5.555
set QuickSortValue[4] = 5.777
set QuickSortValue[5] = -5.111
set QuickSortValue[6] = -5
set QuickSortValue[7] = 0
set QuickSortAscending = false
call QuickSort(0, 7)
call print(0, 7)
endfunction
endscope
JASS:
scope QSortDemoTwo
private struct QSortDemo extends array
private real value
private static integer count = 5
private static integer max = 0
private static method create takes real val returns thistype
set max = max + 1
set thistype(max).value = val
return max
endmethod
private static method callback takes nothing returns nothing
local integer i = 1
call BJDebugMsg("==== Sorted ====")
call QuickSort(1, max)
loop
exitwhen i > count
call BJDebugMsg(I2S(thistype(QuickSortIndex[i])) + " : " + R2S(thistype(QuickSortIndex[i]).value))
set i = i + 1
endloop
endmethod
private static method onInit takes nothing returns nothing
local integer i = 1
local thistype this
call BJDebugMsg("==== Unsorted ====")
loop
exitwhen i > count
set this = thistype.create(GetRandomReal(0, 100))
set QuickSortValue[i] = this.value
set QuickSortIndex[i] = this
call BJDebugMsg(I2S(thistype(i)) + " : " + R2S(thistype(i).value))
set i = i + 1
endloop
call TimerStart(CreateTimer(), 0, false, function thistype.callback)
endmethod
endstruct
endscopeSorters hate that trick
Last edited:
