[General] Problem with Quicksort

[deathismyfriend]

Hello i have a quicksort algorithm that works good but it needs to work with any size of integer array. I don't know how to do that. Right now it sorts from high to low.
Any help is appreciated.

JASS ONLY PLEASE.

triggers

    function H2LPartitionFunc takes integer left, integer right, integer pivot returns integer
        local integer temp1
        call BJDebugMsg( "left = " + I2S( left))
        call BJDebugMsg( "right = " + I2S( right))
        call BJDebugMsg( "pivot = " + I2S( pivot))
        call DisplayTextToPlayer( Player(0), 0, 0, "  ")
        loop
            exitwhen left == right
            loop
                exitwhen udg_h2LGlobalInt2[ left] < udg_h2LGlobalInt2[ pivot] or left == pivot
                call BJDebugMsg( "left < pivot = " + I2S( udg_h2LGlobalInt2[ left]) + " < " + I2S( udg_h2LGlobalInt2[ pivot]))
                set left = left + 1
            endloop
            loop
                exitwhen udg_h2LGlobalInt2[ right] > udg_h2LGlobalInt2[ pivot] or right == pivot
                call BJDebugMsg( "right > pivot = " + I2S( udg_h2LGlobalInt2[ right]) + " > " + I2S( udg_h2LGlobalInt2[ pivot]))
                set right = right - 1
            endloop
            call BJDebugMsg( "left = " + I2S( left))
            call BJDebugMsg( "right = " + I2S( right))
            call BJDebugMsg( "pivot = " + I2S( pivot))
            call DisplayTextToPlayer( Player(0), 0, 0, "  ")
            set temp1 = udg_h2LGlobalInt2[ left]
            set udg_h2LGlobalInt2[ left] = udg_h2LGlobalInt2[ right]
            set udg_h2LGlobalInt2[ right] = temp1
            if left == pivot then
                set pivot = right
            elseif right == pivot then
                set pivot = left
            endif
            
        endloop
        return pivot
    endfunction
    
    function H2LSortFunc1 takes nothing returns nothing
        //it is easier to read with locals
        local integer left = 1 // udg_h2LMinValue
        local integer right = 9 // udg_h2LMaxValue
        local integer pivot
        local integer pivot2
        local integer temp2
        local integer L = left
        local integer L1 = 1
        set udg_h2LGlobalInt2[ 1] = 24
        set udg_h2LGlobalInt2[ 2] = 2
        set udg_h2LGlobalInt2[ 3] = 5
        set udg_h2LGlobalInt2[ 4] = 21
        set udg_h2LGlobalInt2[ 5] = 19
        set udg_h2LGlobalInt2[ 6] = 42
        set udg_h2LGlobalInt2[ 7] = 17
        set udg_h2LGlobalInt2[ 8] = 35
        set udg_h2LGlobalInt2[ 9] = 31
        
        loop
            exitwhen L1 > 9
                call DisplayTextToPlayer( Player(0), 0, 0, I2S( udg_h2LGlobalInt2[ L1]))
            set L1 = L1 + 1
        endloop
        call DisplayTextToPlayer( Player(0), 0, 0, "  ")
        //loop
            //exitwhen right < left 
            set pivot = ( right - left) / 2
            set pivot = H2LPartitionFunc( left, right, pivot)
            call H2LPartitionFunc( left, pivot, ( pivot + left) / 2)
            call H2LPartitionFunc( pivot, right, ( right + pivot) / 2)
            
            call BJDebugMsg( "r pivot = " + I2S( pivot))
        //endloop
            
        call DisplayTextToPlayer( Player(0), 0, 0, "  ")
        set L1 = 1
        loop
            exitwhen L1 > 9
                call DisplayTextToPlayer( Player(0), 0, 0, I2S( udg_h2LGlobalInt2[ L1]))
            set L1 = L1 + 1
        endloop
    endfunction

 

[69stehend]

1. does jass only mean that vjass is ok too?
2. all arrays in warcraft 3 have the size 8192 (though the 8192nd position is bugged and shouldn't be used)
that means you could give H2LSortFunc1 a parameter integer right
so instead of preset right = 9 you could pass the right border to the function on function call
of course you have to adjust your sort function then too (if it's that whats troubling you, just tell. I think i have an implementation of quicksort in java on my computer and i could turn it into jass)
this way you can sort any size of array, you just have to copy the values that shall be sorted into the array udg_h2LGlobalInt2 and pass the right border to the sort function

 

[deathismyfriend]

1) Jass would be easier since i wouldn't have to convert vJass into jass.
2) i know this look in the comments closer. The 1 and 9 are just for testing. The values udg_h2LMinValue ( replaces left) / udg_h2LMaxValue ( replaces right)

Right now this works and yes it is easy to change to any number of values. Problem is it doesn't recursively check the array and end when everything is sorted.

At its current point it works for an array indexed from 1 to 9 but i need it to work with all array sizes. I don't know how to do the recursive check. And how to exit when that check is completed.

 

[chobibo]

edit: I overlooked the jass only part, disregard this.

 

[deathismyfriend]

I just need to know how to recursively check the array until it is completely sorted. Any help is appreciated.

 

[Erkki2]

I don't know if this is of any help, but here's how I would do quicksort (I didn't have time to test this yet):

function quicksort takes integer left, integer right
    local integer pivot = sortableArray[GetRandomInt(left, right)]
    local integer tmp
    local integer nrOfSmall = 0
    
    if left == right then
        return
    endif

    loop
        exitwhen left == right
        if sortableArray[left] > pivot then
            tmp = sortableArray[left]
            sortableArray[left] = sortableArray[right]
            sortableArray[right] = tmp
            
            set right = right - 1
        else
            set left = left + 1
            set nrOfSmall = nrOfSmall + 1
        endif
    endloop

    call quicksort (left, left + nrOfSmall - 1)
    call quicksort (left + nrOfSmall + 1, right)
endfunction