Sorting an Array: Quicksort method!

01-04-2009, 04:17 AM

Ok...i'm trying to reorganize an array of integer values, and i need to put them from the lower to the higher (ok probably i'll need to reverse the order some times, but is not a big trouble)...

Actually the array is 24 index big (0 to 23 so), so it's not a big trouble, but this function is going to be called a lot of times, so i decided that i should use the best alghorithm possible here.

Searching trough the net i found on wikipedia (as always) that the best one is probably the quick sort alghorithm.

Now, i tried to implement it from the C example code but in the first version i created i use "pointers", which should work in jass..but at the end, doesn't do anything!Or better, it doesn't reorder my array...just leave it as it is

Thinking about something "wrong" in jass, i created also a version which "avoid" pointers, or better, works...but this one simply doesn't start the "recursive" point (first time i call the function inside the function...nothing happens ç_ç...no messages..nothing)

here are my two pieces of code, can you help me a bit?it's six hours that i'm working on it...

This is the NO-POINTER version

JASS:

type AggroList extends integer array[24]
    struct qs_partions_result
        AggroList l
        integer low
    endstruct
    function qs_swap takes AggroList l, integer i, integer j returns AggroList
        local AggroList temp=AggroList.create()
        local integer dummy
        set temp=l
        set dummy=temp[j]
        set temp[j]=temp[i]
        set temp[i]=dummy
        return temp
    endfunction
    function qs_partions takes AggroList l, integer low, integer high returns qs_partions_result
        local integer prvotkey
        local qs_partions_result temp=qs_partions_result.create()
        set temp.l=l
        set prvotkey=temp.l[low]
        loop
            exitwhen (low>=high)
            loop
                exitwhen ((low>=high) or (temp.l[high]<prvotkey))
                set high=high-1
            endloop
            set temp.l=qs_swap(l,high,low)
            loop
                exitwhen ((low>=high) or (temp.l[low]>prvotkey))
                set low=low+1
            endloop
            set temp.l=qs_swap(l,high,low)
        endloop
        call DisplayTimedTextToForce(GetPlayersAll(),30.00,"Loop finito big")
        set temp.low=low
        return temp
    endfunction
    function qs_qsort takes AggroList l, integer low, integer high returns AggroList
        local integer prvotloc
        local qs_partions_result temp=qs_partions_result.create()
        set temp.l=l
        set temp.low=low
        if (low<high) then
            set temp=qs_partions(temp.l,low,high)
            call DisplayTimedTextToForce(GetPlayersAll(),30.00,"ok qui")
            set temp.l=qs_qsort(temp.l,low,prvotloc-1)
            call DisplayTimedTextToForce(GetPlayersAll(),30.00,"Iferfer")
            set temp.l=qs_qsort(temp.l,prvotloc+1,high)
        endif
        return temp.l
    endfunction
    function qs_quicksort takes AggroList l, integer dimensione returns AggroList
        local AggroList al=AggroList.create()
        set al=qs_qsort(al,0,dimensione-1)
        return al
    endfunction

and this is the POINTER version

JASS:

type AggroList extends integer array[24]
    function qs_swap takes AggroList l, integer i, integer j returns nothing
        local integer dummy
        set dummy=l[j]
        set l[j]=l[i]
        set l[i]=dummy
    endfunction
    function qs_partions takes AggroList l, integer low, integer high returns integer
        local integer prvotkey
        set prvotkey=l[low]
        loop
            exitwhen (low>=high)
            loop
                exitwhen ((low>=high) or (l[high]<prvotkey))
                set high=high-1
            endloop
            call qs_swap(l,high,low)
            loop
                exitwhen ((low>=high) or (l[low]>prvotkey))
                set low=low+1
            endloop
            call qs_swap(l,high,low)
        endloop
        return low
    endfunction
    function qs_qsort takes AggroList l, integer low, integer high returns nothing
        local integer prvotloc
        if (low<high) then
            set prvotloc=qs_partions(l,low,high)
            call qs_qsort(l,low,prvotloc-1)
            call qs_qsort(l,prvotloc+1,high)
        endif
    endfunction
    function qs_quicksort takes AggroTable l, integer dimensione returns nothing
        call qs_qsort(1,0,dimensione-1)
    endfunction

This is the testing function (actually is set for the NO-POINTER version, it's easy to change it for POINTER version...just convert the sets on the array in calls ...)

...before you say anything about tr=asd, this is only a test function and it's going to be removed...i were making other tests with it and so i left that thing there :P

JASS:

    function pt takes nothing returns nothing
        local AggroList asd=AggroList.create()
        local AggroList tr=AggroList.create()
        local integer i=0
        set asd[0]=23
        set asd[1]=5543
        set asd[2]=434
        set asd[3]=98
        set asd[4]=4705
        set asd[5]=9800
        set asd[6]=5465
        set asd[7]=6934
        set asd[8]=214
        set asd[9]=6564
        set asd[10]=6456
        set asd[11]=0
        set asd[12]=653
        set asd[13]=679
        set asd[14]=2135
        set asd[15]=9568
        set asd[16]=68
        set asd[17]=5684
        set asd[18]=68
        set asd[19]=9645
        set asd[20]=1
        set asd[21]=2
        set asd[22]=3
        set asd[23]=4
        set tr=asd
        call DisplayTimedTextToForce(GetPlayersAll(),30.00,"Begin")
        loop
            exitwhen i>=24
            call DisplayTimedTextToForce(GetPlayersAll(),30.00,I2S(tr[i]))
            set i=i+1
        endloop
        call DisplayTimedTextToForce(GetPlayersAll(),30.00,"--------------------------------")
        set tr=qs_quicksort(tr,24)
        set i=0
        loop
            exitwhen i>=24
            call DisplayTimedTextToForce(GetPlayersAll(),30.00,I2S(tr[i]))
            set i=i+1
        endloop
    endfunction

the C code which i "copied" (yes first i tried to understand, i tried to make it works...nothing worked for a lot of hours, i tried to copy and i'm still here...now it's time to ask for a bit of help i think)

the c code obviusly works, i've tested it also with my values

Code:

#include <stdio.h>

void swap(int l[], int i, int j)
{  int dummy;
   dummy=l[j];
   l[j]=l[i];
   l[i]=dummy;  
 }

int partions(int l[],int low,int high)
{
    int prvotkey=l[low];
    while (low<high)
    {
        while (low<high && l[high]>=prvotkey)
            --high;
        swap(l,high,low);
        while (low<high && l[low]<=prvotkey) 
            ++low;
        swap(l,high,low);      
    }

    return low;
}

void qsort(int l[],int low,int high)
{
    int prvotloc;
    if(low<high)
    {
        prvotloc=partions(l,low,high);    
        qsort(l,low,prvotloc-1); 
        qsort(l,prvotloc+1,high); 
    }
}

void quicksort(int l[],int n)
{
    qsort(l,0,n); 
}

void main()
{
    int a[11]={103,2,32,43,23,45,36,57,14,27,39};
    int b,c;
    for (b=0;b<=10;b++)
        printf("%3d ",a[b]);

    printf("\n");
    quicksort(a,10);

    for(c=0;c<=10;c++)
        printf("%3d ",a[c]);

}

Thanks for help

01-04-2009, 04:46 AM	#2
DioD	You will never code anything better then "generic" methods. You code do nothing to provided array, is work with its own array. http://ru.youtube.com/watch?v=zIgu9q...eature=related view entire video, not everything possible in jass.

01-04-2009, 05:53 AM

Ammorth

Tried messing with your script without results so I pulled up my c++ quicksort and converted it to Jass.

Here you are:

JASS:

function getPartition takes AggroList vals, integer left, integer right, integer pivot returns integer
        local integer temp
        local integer pivotVal = vals[pivot]
        local integer index = left
        local integer i = left
        set vals[pivot] = vals[right]
        set vals[right] = pivotVal
        loop
            exitwhen i >= right
            if (vals[i] <= pivotVal) then
                set temp = vals[i]
                set vals[i] = vals[index]
                set vals[index] = temp
                set index = index + 1
            endif
            set i = i + 1
        endloop
        set vals[right] = vals[index]
        set vals[index] = pivotVal
        return index
    endfunction


    function quickSort takes AggroList vals, integer left, integer right returns nothing
        local integer pivot
        if (right > left) then
            set pivot = GetRandomInt(left, right)
            set pivot = getPartition(vals, left, right, pivot)
            call quickSort(vals, left, pivot - 1)
            call quickSort(vals, pivot + 1, right)
        endif
    endfunction

based from:

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void quickSortInt(int vals[], int left, int right);
void displayArray(int vals[], int size);

int main()
{
	srand((unsigned)time(0)); // sets random seed

	int Data[10]={9,3,5,14,13,7,0,3,1,-3};
	quickSortInt(Data, 0, 9);
	displayArray(Data, 10);
	return 0;
}

void displayArray(int vals[], int size)
{
	for(int i = 0; i < size; i++)
	{
		cout<<vals[i]<<endl;
	}
}

int getRandIntRange(int min, int max)
{
	int range = (max-min+1);
	return (rand()%range)+min;
}

int getPartition(int vals[], int left, int right, int pivot)
{
	int temp;
	int pivotVal = vals[pivot];
	int index = left;
	vals[pivot] = vals[right];
	vals[right] = pivotVal;
	for (int i = left; i < right; i++)
	{
		if (vals[i] <= pivotVal)
		{
			temp = vals[i];
			vals[i] = vals[index];
			vals[index] = temp;
			index++;
		}
	}
	vals[right] = vals[index];
	vals[index] = pivotVal;
	return index;
}


void quickSortInt(int vals[], int left, int right)
{
	if (right > left)
	{
		int pivot = getRandIntRange(left, right);
		pivot = getPartition(vals, left, right, pivot);
		quickSortInt(vals, left, pivot - 1);
		quickSortInt(vals, pivot + 1, right);
	}
}

01-04-2009, 09:05 AM	#4
PitzerMike	This may disappoint you but for smaller array sizes (like 24 in your case) quicksort is slower than the primitive methods like Insertion Sort etc.

01-04-2009, 02:06 PM

Fire-Dragon-DoL

Quote:

Originally Posted by Ammorth

Tried messing with your script without results so I pulled up my c++ quicksort and converted it to Jass.

Here you are:

JASS:

function getPartition takes AggroList vals, integer left, integer right, integer pivot returns integer
        local integer temp
        local integer pivotVal = vals[pivot]
        local integer index = left
        local integer i = left
        set vals[pivot] = vals[right]
        set vals[right] = pivotVal
        loop
            exitwhen i >= right
            if (vals[i] <= pivotVal) then
                set temp = vals[i]
                set vals[i] = vals[index]
                set vals[index] = temp
                set index = index + 1
            endif
            set i = i + 1
        endloop
        set vals[right] = vals[index]
        set vals[index] = pivotVal
        return index
    endfunction


    function quickSort takes AggroList vals, integer left, integer right returns nothing
        local integer pivot
        if (right > left) then
            set pivot = GetRandomInt(left, right)
            set pivot = getPartition(vals, left, right, pivot)
            call quickSort(vals, left, pivot - 1)
            call quickSort(vals, pivot + 1, right)
        endif
    endfunction

based from:

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void quickSortInt(int vals[], int left, int right);
void displayArray(int vals[], int size);

int main()
{
	srand((unsigned)time(0)); // sets random seed

	int Data[10]={9,3,5,14,13,7,0,3,1,-3};
	quickSortInt(Data, 0, 9);
	displayArray(Data, 10);
	return 0;
}

void displayArray(int vals[], int size)
{
	for(int i = 0; i < size; i++)
	{
		cout<<vals[i]<<endl;
	}
}

int getRandIntRange(int min, int max)
{
	int range = (max-min+1);
	return (rand()%range)+min;
}

int getPartition(int vals[], int left, int right, int pivot)
{
	int temp;
	int pivotVal = vals[pivot];
	int index = left;
	vals[pivot] = vals[right];
	vals[right] = pivotVal;
	for (int i = left; i < right; i++)
	{
		if (vals[i] <= pivotVal)
		{
			temp = vals[i];
			vals[i] = vals[index];
			vals[index] = temp;
			index++;
		}
	}
	vals[right] = vals[index];
	vals[index] = pivotVal;
	return index;
}


void quickSortInt(int vals[], int left, int right)
{
	if (right > left)
	{
		int pivot = getRandIntRange(left, right);
		pivot = getPartition(vals, left, right, pivot);
		quickSortInt(vals, left, pivot - 1);
		quickSortInt(vals, pivot + 1, right);
	}
}

does it work?i'll test it

Quote:

Originally Posted by PitzerMike

This may disappoint you but for smaller array sizes (like 24 in your case) quicksort is slower than the primitive methods like Insertion Sort etc.

The problem is that now is 24...but actually can be bigger, i don't know exactly...i put 24, but could be 30,40...dunno

Quote:

Originally Posted by DioD

You will never code anything better then "generic" methods.

You code do nothing to provided array, is work with its own array.

http://ru.youtube.com/watch?v=zIgu9q...eature=related

view entire video, not everything possible in jass.

Well actually i thought that pointers do not exists for array in jass...but i tested with this function:

JASS:

type AggroList extends integer array[24]
function test2 takes AggroList al returns nothing
  set al[0]=12
endfunction
function test1 takes nothing returns nothing
  local AggroList al=AggroList.create()
  set al[0]=50
  call test2(al)
  call DisplayTimedTextToForce(GetPlayersAll(),30.00,I2S(al[0]))
endfunction

What happened?

the message was 12 and not 50 as i expected...

EDIT:
Well, actually i followed the line suggested by PitzerMike, and i looked for insertion sort...found it but i've read also that the shell sort is similar but has less complexity, so i tried to work with it.
I resolved my problem and (strangely) this work with pointers too...so if i do call ss_shellsort(myarray) myarray will be edited without using return...

that's good, here is the code

JASS:

    function ss_shellsort takes AggroList al returns nothing
        local integer i
        local integer j
        local integer increment
        local integer temp
        local integer array_size
        set array_size=al.size
        set increment=3
        loop
            exitwhen ((increment>0)!=true)
            set i=0
            loop
                exitwhen ((i<array_size)!=true)
                set j=i
                set temp=al[i]
                loop
                    exitwhen (((j>=increment) and (al[j-increment]>temp))!=true)
                    set al[j]=al[j-increment]
                    set j=j-increment
                endloop
                set al[j]=temp
                set i=i+1
            endloop
            if ((increment/2)!=0) then
                set increment=increment/2
            elseif (increment==1) then
                set increment=0
            else
                set increment=1
            endif
        endloop
    endfunction

01-05-2009, 11:44 PM	#6
MaD[Lion]	Quicksort is good when u sort something tat is totally random unsorted. But if u repeat sort then bubble, merge, or other sorts are better. Quicksort is uber slow on almost sorted lists

01-06-2009, 01:06 AM

Fire-Dragon-DoL

Quote:

Originally Posted by MaD[Lion]

Quicksort is good when u sort something tat is totally random unsorted. But if u repeat sort then bubble, merge, or other sorts are better. Quicksort is uber slow on almost sorted lists

Uhm you are right, the listed could happen that is almost sorted, expecially in the beginning of the fight...

Uhm i was thinking about:
Is possible to declare a function in this way?

JASS:

function shellsort takes integer array arr, integer dim returns integer array

or in ways like that to "standardize" the method (and avoid using the type AggroList) ?
In case is yes, can you suggest me how can I do a thing like that? I don't find the syntax really >.<

01-06-2009, 01:39 AM

Ammorth

AggroList is a native type of integer, but if you want to use it as the array in the function, you would have to type-cast it:

JASS:

function shellsort takes integer arr, integer dim returns integer
    local AggroList al = arr // not safe, but works
    // do stuff with al
    return al // can return as an int, but would need to be casted in receiving function
endfunction

Much safer to keep the type.

01-06-2009, 03:17 AM

TEC_Ghost

I made an aggro system awhile back and used a Shuffle Sort method, might help.

JASS:

function SortAggro takes unit U returns nothing
local integer Index = GetUnitUserData(U)
local integer Rows = CountUnitsInGroup(UnitAggro[Index].group_AggroTable)
local unit Tempunit = null
local group Tempgroup = CreateGroup()
local group Tempgroup2 = CreateGroup()
local integer l = 1

call GroupAddGroup(UnitAggro[Index].group_AggroTable,Tempgroup)
set l = 1

loop
exitwhen l > Rows
set UnitAggro[Index].sortedaggroammount_AggroTable[l] = 0
        loop
            set Tempunit = FirstOfGroup(Tempgroup) 
        exitwhen Tempunit == null
                if UnitAggro[Index].ammount_AggroTable[GetUnitUserData(Tempunit)] > UnitAggro[Index].sortedaggroammount_AggroTable[l] then
                    set UnitAggro[Index].sortedunits_AggroTable[l] = Tempunit
                    set UnitAggro[Index].sortedaggroammount_AggroTable[l] = UnitAggro[Index].ammount_AggroTable[GetUnitUserData(Tempunit)]
                endif
                
            call GroupAddUnit(Tempgroup2,Tempunit)
            call GroupRemoveUnit(Tempgroup,Tempunit)
        endloop

call GroupRemoveUnit(Tempgroup2,UnitAggro[Index].sortedunits_AggroTable[l])
call GroupAddGroup(Tempgroup2,Tempgroup)
call GroupClear(Tempgroup2)
  
set l=l+1
endloop

endfunction