• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Sorty loops 2

Status
Not open for further replies.
Level 13
Joined
Nov 7, 2014
Messages
571
This is a follow up of Sorty loops which is "Not open for further replies".


I don't know why I didn't think of this earlier but it's very easy to go one step further and make the user do the swapping themselves. This way we avoid the copying from the user's arrays to ours. It also simplifies the implementation:

JASS:
globals
    integer sortstate
    integer sortinita
    integer sortinitb
    integer sorta
    integer sortb
    integer sortcmp
    integer sortIdxA
    integer sortIdxB
endglobals

// sorts the range [a, b)
function sortBegin takes integer a, integer b returns nothing
    set sortstate = 1
    set sortinita = a
    set sortinitb = b
    set sorta = a
endfunction

// uses insertion sort, which is slow for big arrays, but easy-ish to translate
// to a state machine
function sortDone takes nothing returns boolean
    loop
    if 1 == sortstate then
        if sorta == sortinitb then
            return true
        else
            set sortb = sorta
            set sortstate = 2
            // continue
        endif

    elseif 2 == sortstate then
        if sortb <= sortinita then
            set sorta = sorta + 1
            set sortstate = 1
            // continue
        else
            set sortIdxA = sortb - 1
            set sortIdxB = sortb
            set sortstate = 3
            // let the user use the indices 'sortIdxA, sortIdxB' and call 'sortSwap'
            // with the result of the comparison
            return false
        endif

    elseif 3 == sortstate then
        if sortcmp <= 0 then
            set sorta = sorta + 1
            set sortstate = 1
        else
            // because sortcmp > 0 at this point the user should've swapped
            // the values at indices 'sortIdxA' and 'sortIdxB'
            set sortb = sortb - 1
            set sortstate = 2
        endif
        // continue
    endif
    endloop
endfunction

// returns true if the values at indices 'sortIdxA' and 'sortIdxB' need to be swapped
function sortSwap takes integer cmp returns boolean
    set sortcmp = cmp
    return cmp > 0
endfunction

The above fits on a single page (sort of =)) and it's generic in the sense that it can sort any array/struct of any type with any kind of comparison logic (with a bit of help from the user):

JASS:
function sortIntegers takes nothing returns nothing
    local integer array xs
    local integer nxs
    local integer tmpi
    local integer cmp
    local integer a

    set nxs = 10

    // get some array of integers
    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        set xs[a] = GetRandomInt(-5, 5)
    endloop


    // sort it
    call sortBegin(0, nxs)
    loop
        exitwhen sortDone()

        if xs[sortIdxA] < xs[sortIdxB] then
            set cmp = -1
        elseif xs[sortIdxA] > xs[sortIdxB] then
            set cmp = 1
        else
            set cmp = 0
        endif

        if sortSwap(cmp) then
            set tmpi = xs[sortIdxA]
            set xs[sortIdxA] = xs[sortIdxB]
            set xs[sortIdxB] = tmpi
        endif
    endloop
endfunction

Not exactly a one liner but... it is simple. It doesn't require you to use function pointers, functors, lambdas, operator< overloading, implementing 'IComparable' or some other "advanced" language machinery. It also has the advantage of being able to sort parallel arrays easily (try that with your favourite sort implementation).

There's one big down side though... it's slower. It uses insertion sort (which is slow) translated into a state machine (which makes it even slower).

The examples from the other thread but using the new implementation:
JASS:
function writeln takes string s returns nothing
    call DisplayTimedTextToPlayer(GetLocalPlayer(), 0.0, 0.0, 10.0, s)
endfunction

globals
    integer nxs
endglobals

globals
    integer array xsi
endglobals

function printXsi takes nothing returns nothing
    local string s = "["
    local integer a
    local boolean sep = false

    if nxs == 0 then
        call writeln("[]")
        return
    endif

    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        if sep then
            set s = s + ", "
        endif
        set sep = true
        set s = s + I2S(xsi[a])
    endloop
    set s = s + "]"

    call writeln(s)
endfunction

function testSortInts takes nothing returns nothing
    local integer tmpi
    local integer cmp
    local integer a

    set nxs = 10

    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        set xsi[a] = GetRandomInt(-5, 5)
    endloop

    call printXsi()

    call sortBegin(0, nxs)
    loop
        exitwhen sortDone()

        if xsi[sortIdxA] < xsi[sortIdxB] then
            set cmp = -1
        elseif xsi[sortIdxA] > xsi[sortIdxB] then
            set cmp = 1
        else
            set cmp = 0
        endif

        if sortSwap(cmp) then
            set tmpi = xsi[sortIdxA]
            set xsi[sortIdxA] = xsi[sortIdxB]
            set xsi[sortIdxB] = tmpi
        endif
    endloop

    call printXsi()
endfunction

globals
    real array xsr
endglobals

function printXsr takes nothing returns nothing
    local string s = "["
    local integer a
    local boolean sep = false

    if nxs == 0 then
        call writeln("[]")
        return
    endif

    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        if sep then
            set s = s + ", "
        endif
        set sep = true
        set s = s + R2S(xsr[a])
    endloop
    set s = s + "]"

    call writeln(s)
endfunction

function testSortReals takes nothing returns nothing
    local real tmpr
    local integer cmp
    local integer a

    set nxs = 10

    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        set xsr[a] = GetRandomReal(-100.0, 100.0)
    endloop

    call printXsr()

    call sortBegin(0, nxs)
    loop
        exitwhen sortDone()

        if xsr[sortIdxA] < xsr[sortIdxB] then
            set cmp = -1
        elseif xsr[sortIdxA] > xsr[sortIdxB] then
            set cmp = 1
        else
            set cmp = 0
        endif

        if sortSwap(cmp) then
            set tmpr = xsr[sortIdxA]
            set xsr[sortIdxA] = xsr[sortIdxB]
            set xsr[sortIdxB] = tmpr
        endif
    endloop

    call printXsr()
endfunction

globals
    string array xss
endglobals

function printXss takes nothing returns nothing
    local string s = "["
    local integer a
    local boolean sep = false

    if nxs == 0 then
        call writeln("[]")
        return
    endif

    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        if sep then
            set s = s + ", "
        endif
        set sep = true
        set s = s + "'" + xss[a] + "'"
    endloop
    set s = s + "]"

    call writeln(s)
endfunction

function testSortStrings takes nothing returns nothing
    local string tmps
    local integer cmp
    local integer uid
    local unit u
    local integer a

    set nxs = 5

    set a = 0
    loop
    exitwhen a == nxs
        set uid = ChooseRandomCreep(GetRandomInt(0, 10))
        if uid != 0 then
            set u = CreateUnit(Player(0), uid, 0.0, 0.0, 0.0)
            set xss[a] = GetUnitName(u)
            call RemoveUnit(u)
            set a = a + 1
        endif
    endloop

    call printXss()

    call sortBegin(0, nxs)
    loop
        exitwhen sortDone()

        if StringLength(xss[sortIdxA]) < StringLength(xss[sortIdxB]) then
            set cmp = -1
        elseif StringLength(xss[sortIdxA]) > StringLength(xss[sortIdxB]) then
            set cmp = 1
        else
            set cmp = 0
        endif

        if sortSwap(cmp) then
            set tmps = xss[sortIdxA]
            set xss[sortIdxA] = xss[sortIdxB]
            set xss[sortIdxB] = tmps
        endif
    endloop

    call printXss()
endfunction

globals
    unit array xsu
endglobals

function printXsu takes nothing returns nothing
    local string s = "["
    local integer a
    local boolean sep = false

    if nxs == 0 then
        call writeln("[]")
        return
    endif

    set a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        if sep then
            set s = s + ", "
        endif
        set sep = true
        set s = s + GetUnitName(xsu[a])
    endloop
    set s = s + "]"

    call writeln(s)
endfunction

function removeXsu takes nothing returns nothing
    local integer a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == nxs
        call RemoveUnit(xsu[a])
        set xsu[a] = null
    endloop
endfunction

function testSortUnits takes nothing returns nothing
    local player p = Player(0)
    local unit ua
    local unit ub
    local integer ra
    local integer rb
    local integer cmp
    local unit tmpu
    local integer a

    set xsu[0] = CreateUnit(p, 'opeo', 0.0, 0.0, 270.0)
    set xsu[1] = CreateUnit(p, 'Ulic', 0.0, 0.0, 270.0)
    set xsu[2] = CreateUnit(p, 'ewsp', 0.0, 0.0, 270.0)
    set xsu[3] = CreateUnit(p, 'Obla', 0.0, 0.0, 270.0)
    set xsu[4] = CreateUnit(p, 'Udre', 0.0, 0.0, 270.0)
    set xsu[5] = CreateUnit(p, 'ugho', 0.0, 0.0, 270.0)
    set xsu[6] = CreateUnit(p, 'Emoo', 0.0, 0.0, 270.0)
    set xsu[7] = CreateUnit(p, 'Ofar', 0.0, 0.0, 270.0)
    set xsu[8] = CreateUnit(p, 'uaco', 0.0, 0.0, 270.0)
    set xsu[9] = CreateUnit(p, 'Edem', 0.0, 0.0, 270.0)
    set xsu[10] = CreateUnit(p, 'hfoo', 0.0, 0.0, 270.0)
    set xsu[11] = CreateUnit(p, 'Hpal', 0.0, 0.0, 270.0)
    set xsu[12] = CreateUnit(p, 'ogru', 0.0, 0.0, 270.0)
    set xsu[13] = CreateUnit(p, 'earc', 0.0, 0.0, 270.0)
    set xsu[14] = CreateUnit(p, 'Hblm', 0.0, 0.0, 270.0)
    set xsu[15] = CreateUnit(p, 'hpea', 0.0, 0.0, 270.0)
    set nxs = 16

    call printXsu()

    // heroes come first, then units
    // also sort by race: human, orc, undead, nightelf
    //
    call sortBegin(0, nxs)
    loop
        exitwhen sortDone()
        set ua = xsu[sortIdxA]
        set ub = xsu[sortIdxB]

        if IsUnitType(ua, UNIT_TYPE_HERO) and IsUnitType(ub, UNIT_TYPE_HERO) then
            set ra = GetHandleId(GetUnitRace(ua))
            set rb = GetHandleId(GetUnitRace(ub))
            if ra < rb then
                set cmp = -1
            elseif ra > rb then
                set cmp = 1
            else
                set cmp = 0
            endif

        else
            if IsUnitType(ua, UNIT_TYPE_HERO) then
                set cmp = -1
            elseif IsUnitType(ub, UNIT_TYPE_HERO) then
                set cmp = 1
            else
                set ra = GetHandleId(GetUnitRace(ua))
                set rb = GetHandleId(GetUnitRace(ub))
                if ra < rb then
                    set cmp = -1
                elseif ra > rb then
                    set cmp = 1
                else
                    set cmp = 0
                endif
            endif
        endif

        if sortSwap(cmp) then
            set tmpu = xsu[sortIdxA]
            set xsu[sortIdxA] = xsu[sortIdxB]
            set xsu[sortIdxB] = tmpu
        endif
    endloop

    call printXsu()
    call removeXsu()
endfunction
 
Last edited:
Level 13
Joined
Nov 7, 2014
Messages
571
An algorithmic improvement from insertion sort to shellsort:
JASS:
globals
    integer array sortgaps
    integer sortstate
    integer sortn
    integer sortgap
    integer sorta
    integer sortb
    integer sortc
    integer sortcmp
    integer sortIdxA
    integer sortIdxB
endglobals

// must be called once before 'sortDone'
function sortGapsInit takes nothing returns nothing
    set sortgaps[0] = 701
    set sortgaps[1] = 301
    set sortgaps[2] = 132
    set sortgaps[3] = 57
    set sortgaps[4] = 23
    set sortgaps[5] = 10
    set sortgaps[6] = 4
    set sortgaps[7] = 1
    // ngaps = 8
endfunction

// sorts the range [0, n)
function sortBegin takes integer n returns nothing
    set sortstate = 1
    set sortn = n
    set sorta = 0
endfunction

// uses shellsort translated to a state machine
function sortDone takes nothing returns boolean
    loop
    if 3 == sortstate then
        if sortc < sortgap then
            set  sortb = sortb + 1
            set sortstate = 2
            // continue
        else
            set sortIdxA = sortc - sortgap
            set sortIdxB = sortc
            set sortstate = 4
            // let the user use the indices 'sortIdxA, sortIdxB' and call 'sortSwap'
            // with the result of the comparison
            return false
        endif

    elseif 2 == sortstate then
        if sortb >= sortn then
            set sorta = sorta + 1
            set sortstate = 1
        else
            set sortc = sortb
            set sortstate = 3
        endif
        // continue

    elseif 4 == sortstate then
        if sortcmp <= 0 then
            set sortb = sortb + 1
            set sortstate = 2
        else
            set sortc = sortc - sortgap
            set sortstate = 3
        endif
        // continue

    elseif 1 == sortstate then
        if sorta == 8 then // ngaps
            return true
        else
            set sortgap = sortgaps[sorta]
            set sortb = sortgap
            set sortstate = 2
            // continue
        endif
    endif
    endloop
endfunction

// returns true if the values at indices 'sortIdxA' and 'sortIdxB' need to be swapped
function sortSwap takes integer cmp returns boolean
    set sortcmp = cmp
    return cmp > 0
endfunction

Note that 'sortBegin' now takes a single argument 'n' (instead of 'a' and 'b'), i.e it now sorts the range [0, n). If you want to sort some range [a, b), you can do something like the following:
JASS:
function exampleSortRange takes nothing returns nothing
    local integer array xs
    local integer cmp
    local integer tmp
    local integer a
    local integer b
    local integer idxa
    local integer idxb

    set xs[0] = 5
    set xs[1] = 3
    set xs[2] = 2
    set xs[3] = 1
    set xs[4] = 4

    // sort the range [a, b)
    set a = 1
    set b = 4

    call sortBegin(b - a)
    loop
    exitwhen sortDone()

        // offset the sort indices by 'a'
        set idxa = a + sortIdxA
        set idxb = a + sortIdxB

        if xs[idxa] < xs[idxb] then
            set cmp = -1
        elseif xs[idxa] > xs[idxb] then
            set cmp = 1
        else
            set cmp = 0
        endif

        if sortSwap(cmp) then
            set tmp = xs[idxa]
            set xs[idxa] = xs[idxb]
            set xs[idxb] = tmp
        endif
    endloop
endfunction

Here's an example of sorting parallel arrays (sorting multiple arrays, not sorting different parts of a single array in parallel), with no auxiliary allocations and no extra copies:
JASS:
globals
    // our parallel arrays
    integer array arr1
    real array arr2
    string array arr3
endglobals

function exampleSortParallelArrays takes nothing returns nothing
    local integer cmp
    local integer tmpi
    local real tmpr
    local string tmps
    local integer n

    set arr1[0] = 6
    set arr1[1] = 9
    set arr1[2] = 1
    set arr1[3] = 0
    set arr1[4] = 5

    set arr2[0] = 3.14
    set arr2[1] = 6.28
    set arr2[2] = 9.42
    set arr2[3] = 12.56
    set arr2[4] = 15.7

    set arr3[0] = "six"
    set arr3[1] = "nine"
    set arr3[2] = "one"
    set arr3[3] = "zero"
    set arr3[4] = "five"

    set n = 5

    call sortBegin(n)
    loop
    exitwhen sortDone()
        // we sort by the first array
        if arr1[sortIdxA] < arr1[sortIdxB] then
            set cmp = -1
        elseif arr1[sortIdxA] > arr1[sortIdxB] then
            set cmp = 1
        else
            set cmp = 0
        endif

        if sortSwap(cmp) then
            // we simply swap the elements of every array

            set tmpi = arr1[sortIdxA]
            set arr1[sortIdxA] = arr1[sortIdxB]
            set arr1[sortIdxB] = tmpi

            set tmpr = arr2[sortIdxA]
            set arr2[sortIdxA] = arr2[sortIdxB]
            set arr2[sortIdxB] = tmpr

            set tmps = arr3[sortIdxA]
            set arr3[sortIdxA] = arr3[sortIdxB]
            set arr3[sortIdxB] = tmps
        endif
    endloop
endfunction
 
Level 13
Joined
Nov 7, 2014
Messages
571
Relaxed the comparison from '<=>' to just '<', i.e instead of this
Code:
if xs[sortIdxA] < xs[sortIdxB] then
    set cmp = -1
elseif xs[sortIdxB] < xs[sortIdxA]
    set cmp = 1
else
    set cmp = 0
endif
it's now just:
Code:
set lt = xs[sortIdxA] < xs[sortIdxB]

Added a similar interface for binary searching (lower bound and upper bound, obviously much less generic (only for indexed stuff))'.

Example usage of both libs (can be run with jj, requires small modifications for wc3):
Code:
native GetRandomInt takes integer a, integer b returns integer
native I2S takes integer x returns string
native jjPrint takes string s returns nothing
native jjPrintln takes string s returns nothing
native jjExit takes integer errCode returns nothing

function printXs takes integer n, integer array xs returns nothing
    local boolean comma = false
    local integer a = 0 - 1
    loop
    set a = a + 1
    exitwhen a == n
        if comma then
            call jjPrint(",")
        endif
        set comma = true
        call jjPrint(I2S(xs[a]))
    endloop
    call jjPrint("\n")
endfunction

function assertSorted takes integer n, integer array xs returns nothing
    local integer a
    if n <= 1 then
        return
    endif
    set a = 1 - 1
    loop
    set a = a + 1
    exitwhen a == n
        if not (xs[a-1] <= xs[a]) then
            call jjPrintln("NOT sorted")
            call jjExit(1)
        endif
    endloop
endfunction

function randomXs takes integer n returns integer array
    local integer a
    local integer array xs = new integer array
    call arrsetlen(xs, n)
    set a = -1
    loop
    set a = a + 1
    exitwhen a == n
        // set xs[a] = GetRandomInt(0, 99)
        set xs[a] = GetRandomInt(41, 44)
    endloop
    return xs
endfunction

function test takes nothing returns nothing
    local integer array xs
    local integer tmp
    local integer n
    local integer target

    set n = 10
    set xs = randomXs(n)

    call sortBegin(n)
    loop
        exitwhen sortDone()
        if sortSwap(xs[sortIdxA] < xs[sortIdxB]) then
            set tmp = xs[sortIdxA]
            set xs[sortIdxA] = xs[sortIdxB]
            set xs[sortIdxB] = tmp
        endif
    endloop
    call assertSorted(n, xs)
    call printXs(n, xs)

    set target = 42

    call bsBegin(n)
    loop
        exitwhen not bsMakeGuess()
        call bsLowerBound(xs[bsGuess] < target)
    endloop
    if bsGuess != n and xs[bsGuess] == target then
        call jjPrintln("found "+I2S(target)+", lower bound: "+I2S(bsGuess))
    else
        call jjPrintln("could not find "+I2S(target)+", it can be inserted at idx: "+I2S(bsGuess))
    endif

    call bsBegin(n)
    loop
        exitwhen not bsMakeGuess()
        call bsUpperBound(target < xs[bsGuess])
    endloop
    if bsGuess != 0 and xs[bsGuess-1] == target then
        call jjPrintln("found "+I2S(target)+", upper bound: "+I2S(bsGuess))
    else
        call jjPrintln("could not find "+I2S(target)+", it can be inserted at idx: "+I2S(bsGuess))
    endif
endfunction

function main takes nothing returns nothing
    call test()
endfunction
 

Attachments

  • sorter.j
    2.2 KB · Views: 21
  • binarysearcher.j
    1.6 KB · Views: 31
Status
Not open for further replies.
Top