Sort Multiboard?

04-25-2006, 02:45 PM	#1
MasterofSickness	I have read a lot of posts and finally I also found one which described the same problem that I have at the moment. The only thing with it was, that noone answered or even replied to this thread . So here is the link to the prob I have right now: http://www.wc3campaigns.net/showthre...ort+multiboard Would be good if someone has an idea...

04-25-2006, 03:09 PM

Vuen

You really don't need to worry about the speed of your sorting algorithm with only 12 players. Unless you're worried about stability, the easiest way is to do a simple selection sort on the player array. You can also modify selection sort to be stable.

Altering the multiboard does not generate (much) net traffic. The trigger is run on each player's individual computer, and the only net traffic is to make sure the game doesn't desync.

Using a hidden leaderboard would work perfectly, and wouldn't require you to write any sorting algorithm.

04-25-2006, 04:53 PM

weaaddar

insertion sort is generally speaking a very easy algorithm, and with such a small list of items the speed should be neglible compared to something like quicksort.It is also the best O(n^2) algorithm, with an avg case of n^2/4 and linear in bestcase. It's a stable sort and it can be done in place.
assume udg_p[i] is an array of players, and udg_v[i] the values you want sorted, and udg_num is the number of players in the map.

JASS:

function insertionSort takes nothing returns nothing
    local int i=1
    local int j
    local int v
    local player p
    loop
         exitwhen i==udg_num
         set v=udg_v[i]
         set p=udg_p[i]
         set j=i-1
         loop 
             exitwhen j<1 or udg_v[j]<=v
             set udg_v[j+1]=udg_v[j]
             set udg_p[j+1]=udg_p[j]
             set j=j+1
        endloop
       set udg_v[j+1]=v
       set udg_p[j+1]=p
       set i=i+1
    endloop
endfunction

04-25-2006, 06:19 PM

MasterofSickness

Sorry for late review, but I tried to help in another thread...
So back to Telamon and my problem...

Code:

insertion sort is generally speaking a very easy algorithm, and with such a small list of items the speed should be neglible compared to something like quicksort

@weaaddar
So you think that the code you wrote in JASS is better then the use of a hidden leaderboard?
And if yes:
I'm not so far that I understand this code completely.
The biggest problem I have is, how can you refer with it to the multiboard?
Can you please give a short example? Because when it's faster then using a hidden leaderboard I would prefer to use this "insertion sort".

Thanks so far Vuen & Weaaddar !

04-25-2006, 06:55 PM

PipeDream

The multiboard in aftermath is bubbled. it works fine, 10-12 items is nothing.

however, all the cool kids are using heap sort. you do want to be cool, don't you?

JASS:

//sorted initialized to 0,1,2,3,4...
//afterwards, sorted is ordered to index priority[] in decreasing order
    set nhs = n
    set i = nhs /2
    loop  //Transcribed from [url]http://en.wikipedia.org/wiki/Heapsort[/url]
        if(i > 0) then
            set i = i - 1
            set t = sorted[i]
        else
            set nhs = nhs - 1
            exitwhen nhs <= 0
            set t = sorted[nhs]
            set sorted[nhs] = sorted[0]
        endif

        set parent = i
        set child = i+i+1
        loop
            exitwhen child >= nhs
            if(child + 1 < nhs and priority[sorted[child+1]] < priority[sorted[child]]) then
                set child = child + 1
            endif
            if(priority[sorted[child]] < priority[t]) then
                set sorted[parent] = sorted[child]
                set parent = child
                set child = parent+parent+1
            else
                exitwhen true
            endif
        endloop
        set sorted[parent] = t
    endloop

To use any of these sorts, keep all your data in arrays. Each time you feel like sorting , reset all the multiboard elements to the new values, rather than trying to inplace sort.

04-25-2006, 10:12 PM

weaaddar

Pipedream as much of an epenis it might give you to use heapsort, you have to realize that its actually worse then in insertion sort on lists of a dozen elements. (building the heap operation is nontrivial).

Heapsort is an unstable but can be in place. Its one of the slower n*log(n) sorts, and will lose to insertion sort on a small lists (roughly speak sub 100 elements) since insertion sort on avg is n^2/4, (atleast hte implementation above), and building the heap a lone requires 2*n*log2(n), when n=12, we see that insertion sort absolutely wipes the floor with a time of only 36, but merely to build the heap requires ~87 operations!

On small array you should never incur n*log(n) sorts unless your in a functional language with lists, in which case its probably easier to implement merge sort then even insertion sort.

Stick with insertion sort. The only reason to use this method vs a multiboard is just that its in place and clean.

All you have to do is call insertionSort() and then build a leaderboard with the values located at p[i] for the player and v[i] for the value. I don't remember how leaderboard work at all. I just did this totally from memory so my code may not compile.

04-26-2006, 03:35 PM

MasterofSickness

@ weaaddar
I'm currently working on your jass code and
I want to ask whether there is a difference or not using following line:

1)

JASS:

set udg_v[j+1]=udg_v[j]

or
2)

JASS:

set udg_v[j]=udg_v[j+1]

Does these two lines do the same or is there a difference?
I'm little confused

You wrote

JASS:

set udg_v[j+1]=udg_v[j]

, but if it is the same like the one above, I would prefer to use

JASS:

set udg_v[j]=udg_v[j+1]

,
because this line makes more sense to me, because I always think that the varaible next to the "set" - command gets a new value and not the variable next to the variable next to "set".

EDIT:
At the moment I have the following, but when I try to use the trigger an error about expected a variable name is shown (Integer "LocalInteger_Kills" is an array and Player "LocalPlayer" is an array ; all 4 variables I use are defined in the variables dialog, do I have to use 4 or 8 different variables? I don't understand the difference between v and udg_v, means, I don't know when to use "udg_" in front of the variable and when not! Can anyone explain please?):

Trigger:

Insertion Sort

Events

Conditions

Actions

Custom script: local integer udg_LocalInteger=1

Custom script: local integer udg_LocalInteger_Sort

Custom script: local integer udg_LocalInteger_Kills

Custom script: local player udg_LocalPlayer

Custom script: loop

Custom script: exitwhen udg_LocalInteger==12

Custom script: set LocalInteger_Kills=udg_LocalInteger_Kills[LocalInteger]

Custom script: set LocalPlayer=udg_LocalPlayer[LocalInteger]

Set LocalInteger = (LocalInteger + 1)

Custom script: endloop

04-26-2006, 10:21 PM

PipeDream

Those two lines do different things. Set assigns the value of the right expression to the left variable.
For example, suppose A = 4 and B = 3.
set A = B results in A = 3, B = 3
set B = A results in A = 4, B = 4

The real name of any global variable is udg_<variable editor name>. You use the real udg_name whenever you write custom script. Only use the variable editor name, without udg, when you are pulling something down from a GUI menu.
Four more udg's should do it:

Trigger:

Custom script: set udg_LocalInteger_Kills=udg_LocalInteger_Kills[udg_LocalInteger]

Custom script: set udg_LocalPlayer=udg_LocalPlayer[udg_LocalInteger]

---
I strongly recommend you bite the bullet and convert the trigger to custom text.

04-27-2006, 03:23 PM

weaaddar

you shouldn't use locals except for the ones declared in my function. Convert the trigger to custom text once your convinced the event is correct. Then copy and paste my code into your favorite texteditor and do word replaces for p to LocalPlayer and v to kills or whatever.

assignment is as follows
set variable=(expression).
udg_v[i] is a variable, and an expression. Think of it like mathamatics, you say things like Let n=1, but then meddling through your proof you may actually assign some othing value in terms of n.
Like a proof by induction on a recurrence relation:
If A[n]=2*A[n-1] and A[1]=1 then A[n]=2^(n-1)
Proof:
Basis step:
Let n=1, A[1]=1=2^(1-1) which is what we want.
Inductive Step:
Assume for some n, A[n]=2^(n-1), it will suffice to show for n+1 that A[n+1]=2^(n).
A[n+1]=2*A[n]
A[n+1]=2*(2^n-1) (By our inductive hypothesis)
A[n+1] = 2^n
QED.

04-27-2006, 09:16 PM

#10

MasterofSickness

Quod erat demonstrandum - Which was to be proven

Do you study or how old are you weaaddar, if I may ask?
Yeah, I understood that you set for n = n+1, and the rest of math, but now I really need help on understanding the trigger in comparison to the multiboard. Please read forward to my example...

@ PipeDream
Ok, thanks, I understand now what I thought wrong with these two lines.
I was really a little confused (perhaps because I sat to long in front of my pc

...)

By writing an example I also understand even more, but still in the example I see no way to use the variables sensible for sorting a multiboard.
So first of all here's my example, I hope I understood the code right!

So lets say we have 8 human players in the game for which the multiboard should sort the respectively kills in a decreased order.
udg_num has to be 8 then, or?
Hope so, then further:

Players--Kills
1-------10
2-------15
3-------5
4-------20
5-------0
6-------30
7-------15
8-------0

After using this insertion code, the multiboard should look like this:

Players--Kills
6-------30
4-------20
2-------15
7-------15
1-------10
3-------5
5-------0
8-------0

But I have no idea which variables how to use *argh*
So here is what I brought to paper (image):

Click image for larger version

Name: Insertion Sort.jpg
Views: 15
Size: 285.3 KB
ID: 5131

What I need is an example on how to refer between the "insertion sort" trigger and a multiboard.

Hey, I also get the trigger to work in GUI, but as I said, I have no idea how to connect it to a multiboard. So here is my trigger in GUI and in JASS (please note that I want to stay writing in GUI using custom scripts):

1) GUI:

Trigger:

Insertion Sort

Events

Conditions

Actions

Custom script: local integer udg_IntLocalA=1

Custom script: local integer udg_IntLocalB

Custom script: local integer udg_IntLocalKills

Custom script: local player udg_PlayerLocal

Custom script: loop

Custom script: exitwhen udg_IntLocalA==8

Custom script: set udg_IntLocalKills=udg_IntAr_Values[udg_IntLocalA]

Custom script: set udg_PlayerLocal=udg_PlayerAr[udg_IntLocalA]

Set IntLocalB = (IntLocalA - 1)

Custom script: loop

Custom script: exitwhen udg_IntLocalB<1 or udg_IntAr_Values[udg_IntLocalB]<=udg_IntLocalKills

Custom script: set udg_IntAr_Values[udg_IntLocalB+1]=udg_IntAr_Values[udg_IntLocalB]

Custom script: set udg_PlayerAr[udg_IntLocalB+1]=udg_PlayerAr[udg_IntLocalB]

Set IntLocalB = (IntLocalB + 1)

Custom script: endloop

Custom script: set udg_IntAr_Values[udg_IntLocalB+1]=udg_IntLocalKills

Custom script: set udg_PlayerAr[udg_IntLocalB+1]=udg_PlayerLocal

Set IntLocalA = (IntLocalA + 1)

Custom script: endloop

2) JASS:

JASS:

function Trig_Insertion_Sort_Actions takes nothing returns nothing
    local integer udg_IntLocalA=1
    local integer udg_IntLocalB
    local integer udg_IntLocalKills
    local player udg_PlayerLocal
    loop
    exitwhen udg_IntLocalA==8
    set udg_IntLocalKills=udg_IntAr_Values[udg_IntLocalA]
    set udg_PlayerLocal=udg_PlayerAr[udg_IntLocalA]
    set udg_IntLocalB = ( udg_IntLocalA - 1 )
    loop
    exitwhen udg_IntLocalB<1 or udg_IntAr_Values[udg_IntLocalB]<=udg_IntLocalKills
    set udg_IntAr_Values[udg_IntLocalB+1]=udg_IntAr_Values[udg_IntLocalB]
    set udg_PlayerAr[udg_IntLocalB+1]=udg_PlayerAr[udg_IntLocalB]
    set udg_IntLocalB = ( udg_IntLocalB + 1 )
    endloop
    set udg_IntAr_Values[udg_IntLocalB+1]=udg_IntLocalKills
    set udg_PlayerAr[udg_IntLocalB+1]=udg_PlayerLocal
    set udg_IntLocalA = ( udg_IntLocalA + 1 )
    endloop
endfunction

//===========================================================================
function InitTrig_Insertion_Sort takes nothing returns nothing
    set gg_trg_Insertion_Sort = CreateTrigger(  )
    call TriggerAddAction( gg_trg_Insertion_Sort, function Trig_Insertion_Sort_Actions )
endfunction

Attached Images

Insertion Sort.jpg (285.3 KB)

04-28-2006, 04:10 AM

#11

weaaddar

I'm a computer science student if it wasn't obvious. I also made a mistake. It should be j=j-1. whoops.
Also don't use udg_ for your local variables. You should only use at most one udg_ local for your trigger. And it appears you don't need any for this trigger, anyway. It's much easier to read your code if your format it like I did, get rid of those long bulky var names. udg_IntLocalA is way too long and doesn't really tell you anything. i is much easier on the eyes.

Anyway here is a very quick explanation as to what the algorithm does.

You start at index 1 (arrays start at 0), and say is this element in the right spot? If it isn't shift every element up one until you find one element that is bigger then this. Once you find it, place the element in that index.

Consider this example from a halfway sorted array
10
20
30
40
15 <- index at currently.
---
10
20
30
40<- next index
40
---
10
20
30 <- index
30
40
---
10
20<-- next index
20
30
40
---
10<-- no need to go further
10
20
30
40
---
10
15 <-- this is the correct spot
20
30
40
---
10
15
20 <-- good spot
30
40
---
10
15
20
30 <-- correct spot
40
---
10
15
20
30
40 <-- correct spot
---
Array is sorted.

04-28-2006, 03:40 PM

#12

MasterofSickness

1)
So where exactly lies the mistake?,
is it in the 2nd loop where j=j+1,
so if i'm right I have to use j=j-1 instead of j=j+1?
EDIT: As I said, this replacement should be right (figured out by myself).
2)
Only short question:
When I'm in the 2nd loop for the first time and say that
v[1] = v[0] and
p[1] = p[0]
what does it declare there?,
I mean I have 8 player (p[1-8]) and so I have 8 values (v[1-8])!
So what is p[0] and v[0]?

If p[0] and v[0] were 0,
then the whole algorithm would just set all values from p[1-8] and v[1-8] to 0,
and there nothing is sorted or?
Edit: Also figured out by myself (p[0] and v[0] will never come to use, because of the "exitwhen")

04-29-2006, 08:17 PM	#13
MasterofSickness	Oh my god, I think I understood. The mistake I made was that I thought I had to sort in this way: 1----10 2----15 3----5 4----20 5----0 6----30 7----15 8----0 but with this sort algorith I have to sort in this way: 8----10 7----15 6----5 5----20 4----0 3----30 2----15 1----0 Yay! I think this was my problem, so now I have to see if I get it to work. I will inform you soon.

04-29-2006, 09:10 PM

#14

MasterofSickness

Ah, I made out another thing I thought wrong:
I was sure that when the command "exitwhen x<y" appears and its conditions are true, then the commands between this "exitwhen" and the "endloop" are still run for one last time, BUT that is not true! Ha!
When the condition in the "exitwhen"-command is true, then the loop is immediately quitted. Man that was a hard nut

Although, the command "exitwhen" in fact already say this

Fine for now, but still no working multiboard with this algorithm.
Write back when I'm further!

04-29-2006, 10:06 PM	#15
MasterofSickness	I understand this algorithm quite good now and I have to ask: "Man! Who created this algorithm?! It is genius! Very good idea!" But still I have one problem. Is there perhaps still another mistake in the trigger? I mean "udg_num" (the variable set up for player range) should be number of players in the map + 1, or? If not then the player in the last index position will not be implemented or?