Sort Algorithms

09-26-2009, 03:44 PM

I need a fast sort algorithm to sort lots of integers.
I've made a demo lib containing Quicksort and Selectionsort (and a new array def, cuz i donno how to give arrays to a func)

Functions

vJass:

library sort

globals
    constant integer MAXARRAYSIZE=8000
endglobals

struct Array
    private integer length
    private integer array arr[MAXARRAYSIZE]
    
    static method create takes nothing returns Array
        local Array this
        call this.allocate()
        return this
    endmethod
    
    method getValue takes integer index returns integer
        if index>this.length then
            return 0
        endif
        return this.arr[index]
    endmethod
    
    method setValue takes integer index, integer val returns boolean
        if index>=MAXARRAYSIZE then
            return false
        endif
        if index>this.length then
            set this.length=index
        endif
        set this.arr[index]=val
        return true
    endmethod
    
    method getLength takes nothing returns integer
        return this.length
    endmethod
    
    method remove takes nothing returns nothing
        call this.destroy()
    endmethod    
endstruct

private function swap takes Array a, integer i, integer j returns nothing
    local integer temp=a.getValue(i)
    call a.setValue(i,a.getValue(j))
    call a.setValue(j,temp)
endfunction

private function minimumPosition takes Array a, integer from returns integer
    local integer minpos=from
    local integer i=from+1
    loop
        exitwhen i>=a.getLength()
        
        if a.getValue(i)<a.getValue(minpos) then
            set minpos=i
        endif
        
        set i=i+1
    endloop
    return minpos
endfunction

private function divide takes Array a, integer l, integer r returns integer
    local integer i=l
    local integer j=r-1
    local integer pivot=a.getValue(r)
    loop
        loop
            exitwhen a.getValue(i)>pivot or i>=r
            set i=i+1
        endloop
        loop
            exitwhen a.getValue(j)<pivot or j<=l
            set j=j-1
        endloop
        if i<=j then
            call swap(a,i,j)
            set j=j-1
            set i=i+1
        endif
        exitwhen i>j
    endloop
    if a.getValue(i)>pivot then
        call swap(a,i,r)
    endif
    return i
endfunction

private function qsort takes Array a, integer l, integer r returns nothing
    local integer t
    if l<r then
        set t=divide(a,l,r)
        call qsort(a,l,t-1)
        call qsort(a,t+1,r)
    endif
endfunction

function Selectionsort takes Array a returns nothing
    local integer minpos
    local integer i=0
    loop
        exitwhen i>=a.getLength()-1
        set minpos=minimumPosition(a,i)
        call swap(a,minpos, i)
        set i=i+1
    endloop
endfunction

function Quicksort takes Array a returns nothing
    call qsort(a,0,a.getLength())
endfunction
endlibrary

the points are:
a) which one is faster
b) are there better ones (with code)
c) what to improve
d) do they work properly

Can't test myself cause we got on strike yesterday evening and I didn't get it working properly (hope the code is without compiling errors)

09-26-2009, 04:40 PM	#2
chobibo	I don't fully understand how quicksort works, hence I cannot judge your implementation, but I have to say that quicksort outperforms selection sort with regards to it's average case performance.

09-26-2009, 05:00 PM	#3
Tot	Ok, but cause of blizzs strange jass flaws, I thrust a benchmark more than you (don't be upset, I respect you, but I need to be sure)

09-26-2009, 09:21 PM	#4
weaaddar	No numbers really needed. Its avg case N^2 vs avg case n*log(n). Even on the worse input cases for quicksort (an already sorted list), you should be looking at par performance. As for passable arrays there aren't any, but you can use operators[] or use a global variable to test your sorter.

09-27-2009, 06:08 AM	#5
MaD[Lion]	if u wanna sort integers i recommend u look up radix sort, people dont hear about it alot since its application is mostly on sorting numbers, especially integers. But its performance is totally amazing, ive tried it myself and really loved it. It is comparable to quick/merge sort. it performs at O(kn) worst case, or just O(n) if k is constant. anyway link: http://en.wikipedia.org/wiki/Radix_sort

09-27-2009, 12:52 PM	#6
Tot	@MaD[Lion]: I don't think that radixsort is working for struct-integers (: jasshelper creates integervalues for structs)

09-27-2009, 07:15 PM	#7
PipeDream	I vaguely recall, probably for DARY, that it helped to switch from a recursive n log n sort, either quicksort or mergesort, to an n^2 sort, probably insertion, at around n=10. Helped means quantity of things you could sort before hitting the op limit.

09-29-2009, 07:40 AM	#8
MaD[Lion]	tot: u can use radixsort for anything, if ur object/struct has an integer key JASS: struct RadixClass integer key endstruct //... struct YourStruct extends RadixClass ... endstruct