best way to: Store the units with highest custom value first in a unit array?

[polo2005]

I'm looking for a smart way to store the unit with highest custom value from a unit_Group with x units inside.
for example
unit 1 have the custom value 5
unit 2 have the custom value 3
unit 3 have the custom value 3
unit 4 have the custom value 2

and in my unit_variable
unit 1 should be = unit_variable[1]
unit 2 or unit 3 should be = unit_variable[2] or [3]
unit 4 should be = unit_variable[4]

 

[Darthfett]

Essentially you want it to always be ordered by whichever unit(s) have the highest custom value?

 

[polo2005]

well this is kinda a one set unit_variable so the unit with the highest custom value at that point should come first.

 

[Accname]

You could iterate through all units in the unit-group repeatedly looking for the unit with the lowest custom value, removing it from the unit group, and adding it to the end of the array. This is a simple way, there are better methods, but with GUI it would take alot of work to implement them, more work then i think would be worth it.

Do you need to run this process several times with low time spans in between? If not, go for my suggestion.

 

[polo2005]

that will prob work, but sounds like it will take alot of time to implant this, would it be possible to do this smothly in jass (not vjass, i got zero experience with vjass)? if so, mind giving me an example?

 

[huanAk]

easy, here is how it do in GUI trigger:

   temp_unit 
   temp_integer = 0
   for every loop integer A from 0 to (count units in unit_group-1) do multiple action
		for every unit in unit_group do multiple action
			if custom value of picked unit > temp_integer
				temp_integer = custom value of picked unit
				temp_unit = picked unit
		else do nothing	
		unit_array[loop integer A] = temp_unit	 // unit_array[0] is highest
                remove temp_unit from uni_group

 

[huanAk]

I don't like vJASS, too much trouble for learner/average mapper

 

[polo2005]

wouldn't this only store the unit with highest custom value correctly?

 

[Dirac]

I don't like vJASS, too much trouble for learner/average mapper

That's GUI.

Check this out

 

[polo2005]

That's GUI.

Check this out

That's GUI.

Check this out

very nice, does this req jassnewgen to run? or a patch after 1.21?

 

[Dirac]

I think 1.21 is fine since it dosn't use a hashtable, but yes, requires NewGen

 

[polo2005]

well nor do i so wouldn't know, but its for a req on a system for my brother so i pray it will work for him thanks alot

 

[huanAk]

wouldn't this only store the unit with highest custom value correctly?

did you try ?
- it sorted every unit in your unit group,
- and store them in array, order by custom value (from highest to lowest)

It is GUI trigger which only take a few click.

I don't understand why you need to
- download 2 page of code from other people and
- require NewGen
- require average or higher JASS knowledge to modified
- and it may not work in future patch (eg so many people use these S2I function and it not longer work)

 

[Dirac]

Because your answer is extremely slow, what you're doing there is called a bubble sort and it's exponentially slower for every unit inside the group. I use merge sort which is quite fast. There are other methods that are faster, but mine works for sorting array variables inside structs very well

 

[huanAk]

Because your answer is extremely slow, what you're doing there is called a bubble sort and it's exponentially slower for every unit inside the group. I use merge sort which is quite fast. There are other methods that are faster, but mine works for sorting array variables inside structs very well

Wrong,
"bubble sort" is compare every adjacent pair (Best case= N, worse case= N^2
mine is "selection sort" which pick highest unit in every turn (always N^2)

merge sort may have better average case ( N*logN ). but it may slower because :
- math compare is so fast, so N^2 compare won't take many CPU "operation"
- extra function, variablle, operation in Merg Sort mean it end up more CPU operation that just basic "selection sort"

remember, you are not soring million of unit, so the simplest "selection sort" = fastest sort

 

[Smitty]

He's using shell sort here (that is to say in the linked page), very nice

 

[GFreak45]

you are not soring million of unit, so the simplest "selection sort" = fastest sort

You can't definiteavely say that, any thread on here once answered is kept for later use with the search function and how many units are being sorted and stores differs from map to map. My map stores every single unit's custom data and has to frequently sort large groups, the merge sort method is much faster overall if the group is any larger than 10 units and at that small of a group your method's speed won't create any difference noticeable to anyone playing on a system more advanced than win98 with a shitty processor. The merge sort method takes the same amount of time for any ammount of units, the only increase in time would be if they want every single unit's position (in line) saved and even then I can think of a way to do it with the smallest possible ammount of functions.

 

[SerraAvenger]

Wrong,
"bubble sort" is compare every adjacent pair (Best case= N, worse case= N^2
mine is "selection sort" which pick highest unit in every turn (always N^2)

merge sort may have better average case ( N*logN ). but it may slower because :

Just for the record:
bubblesort and selection sort are ALWAYS n*(n-1)/2 [EDIT:Bubblesort can be n, please read #19 and #20]
mergesort is ALWAYS n log n

Which means that for more than 3 units, mergesort will be faster.
Let us say that because of the additional stack overhead, mergesort has a constant of 10 as opposed to a constant of 1 in selection sort.
Then after 11 units, mergesort is faster.

Back to your problem: if you only need the unit with the lowest custom value, use a heap. if values are changed constantly, use a self-balancing search tree.

 

[Darthfett]

Just for the record:
bubblesort and selection sort are ALWAYS n*(n-1)/2

Bubblesort has a best case scenario of O(n), which is when the input is already sorted. It only goes through the list if it swapped any values in the first pass. This "n*(n-1)/2" is exactly the same as saying O(n^2), because constant values are negligible given that the input is 'big enough'.

mergesort is ALWAYS n log n

No one said it wasn't. Your point after this is still valid, however.

merge sort may have better average case ( N*logN ). but it may slower because :
- math compare is so fast, so N^2 compare won't take many CPU "operation"
- extra function, variablle, operation in Merg Sort mean it end up more CPU operation that just basic "selection sort"

This is only true if the input is sufficiently small, and/or partially sorted already (iff the algorithm has a better best-case scenario), which are rare cases.

 

[SerraAvenger]

Bubblesort has a best case scenario of O(n), which is when the input is already sorted. It only goes through the list if it swapped any values in the first pass.

You're absolutely right. I looked up bubblesort and found out that it uses a clever condition to exit early when the array was sorted. The sorting algorithm I had in mind didn't do that (and hence was in Theta(n^2)). Not that it mattered much though ; )

This "n*(n-1)/2" is exactly the same as saying O(n^2), because constant values are negligible given that the input is 'big enough'.

Jup.