Merge Sort [GUI Friendly] v1.01

This bundle is marked as approved. It works and satisfies the submission rules.

Merge-sort-example-300px.gif



Code
JASS:
//              Merge Sort [GUI Friendly] v1.01
//                    by Flux
//      http://www.hiveworkshop.com/forums/members/flux/
//
//      Merge Sort is an efficient sorting algorithm
//      that has a worst case performance of O(n logn)
//      This system allows you to sort values of an array
//      in either ascending or descending order
//      Additionally, it this system allows you to get the
//      sorted indices of the array values.
//
//      Purely written in JASS and doesn't require anything


function MSort_Display takes nothing returns nothing
    local integer i = udg_MSort_StartIndex
    call BJDebugMsg("========== |cffffcc00[Merge Sort]:|r Data ===============")
    loop
        exitwhen i > udg_MSort_EndIndex
        call BJDebugMsg("MSort_Values[" + I2S(i) + "] = " + R2S(udg_MSort_Values[i]) + ", MSort_Indices[" + I2S(i) + "] = " + I2S(udg_MSort_Indices[i]))
        set i = i + 1
    endloop
    call BJDebugMsg("============== End Display =================\n")
endfunction

function MSort_Merge takes integer leftStart, integer leftEnd, integer rightStart, integer rightEnd returns nothing
    local integer i = leftStart
    local integer j = rightStart
    local integer k = i
    loop
        exitwhen i > leftEnd or j > rightEnd
        if udg_MSort_Ascending then
            if udg_MSort_Left[i] < udg_MSort_Right[j] then
                set udg_MSort_Values[k] = udg_MSort_Left[i]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
                set k = k + 1
                set i = i + 1
            else 
                set udg_MSort_Values[k] = udg_MSort_Right[j]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
                set k = k + 1
                set j = j + 1
            endif
        else
            if udg_MSort_Left[i] > udg_MSort_Right[j] then
                set udg_MSort_Values[k] = udg_MSort_Left[i]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
                set k = k + 1
                set i = i + 1
            else 
                set udg_MSort_Values[k] = udg_MSort_Right[j]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
                set k = k + 1
                set j = j + 1
            endif
        endif
    endloop
    //Fill up remaining
    loop
        exitwhen i > leftEnd
        set udg_MSort_Values[k] = udg_MSort_Left[i]
        set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
        set k = k + 1
        set i = i + 1
    endloop
    loop
        exitwhen j > rightEnd
        set udg_MSort_Values[k] = udg_MSort_Right[j]
        set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
        set k = k + 1
        set j = j + 1
    endloop
    //Update IndexInitial
    set i = leftStart
    loop
        exitwhen i == k
        set udg_MSort_IndexInitial[i] = udg_MSort_Indices[i]
        set i = i + 1
    endloop
endfunction

//Recursive Function
function MSort_Merge_Sort takes integer start, integer end returns nothing
    local integer i = start
    local integer mid
    if end - start >= 1 then
        set mid = (end + start)/2
        call MSort_Merge_Sort(start, mid)
        call MSort_Merge_Sort(mid+1, end)
        loop
            exitwhen i > mid
            set udg_MSort_Left[i] = udg_MSort_Values[i]
            set i = i + 1
        endloop
        loop
            exitwhen i > end
            set udg_MSort_Right[i] = udg_MSort_Values[i]
            set i = i + 1
        endloop
        call MSort_Merge(start, mid, mid+1, end) 
        //call MSort_Display()
        // ^uncomment to display values
    endif
endfunction


function Trig_Merge_Sort_Main takes nothing returns boolean
    call MSort_Merge_Sort(udg_MSort_StartIndex, udg_MSort_EndIndex)
    return false
endfunction

//===========================================================================
function InitTrig_Merge_Sort takes nothing returns nothing
    set gg_trg_Merge_Sort = CreateTrigger()
    call TriggerAddCondition(gg_trg_Merge_Sort, Condition(function Trig_Merge_Sort_Main))
endfunction


JASS:
//
//      MERGE SORT READ ME
//
//          ***********************************************
//          ************** HOW TO IMPORT ******************
//          ***********************************************
//
//       1. Copy the Merge Sort Variable Creator in your map.
//          Make sure you set the "Automatically create unknown variables
//          while pasting trigger data" in Files -> Preferences.
//          After copying, delete Merge Sort Variable Creator
//       2. Copy the 'Merge Sort' trigger to your map.
//
//
//
//          **********************************************
//          *************** HOW TO USE *******************
//          **********************************************
//
//      1. Store the values you want to sort to MSort_Values
//         and initialize MSort_IndexInitial[n] = n
//       Example:
//        MSort_Values[0] = 3
//        MSort_IndexInitial[0] = 0
//        MSort_Values[1] = 9
//        MSort_IndexInitial[1] = 1
//        MSort_Values[2] = 4
//        MSort_IndexInitial[2] = 2
//        MSort_Values[3] = 5
//        MSort_IndexInitial[3] = 3
//        MSort_Values[4] = 2
//        MSort_IndexInitial[4] = 4
//
//      2. Set MSort_Ascending, MSort_StartIndex, MSort_EndIndex
//       Example:
//        MSort_Ascending = true 
//        MSort_StartIndex = 0
//        MSort_EndIndex = 4
//
//      3. Run Merge Sort <gen> (checking Conditions)
//      
//      4. The Array new values are now:
//
//        MSort_Values[0] = 2
//        MSort_Values[1] = 3
//        MSort_Values[2] = 4
//        MSort_Values[3] = 5
//        MSort_Values[4] = 9
//
//        MSort_Indices[0] = 4    ; from MSort_Values[4] = 2
//        MSort_Indices[1] = 0    ; from MSort_Values[0] = 3
//        MSort_Indices[2] = 2    ; from MSort_Values[2] = 4
//        MSort_Indices[3] = 3    ; from MSort_Values[3] = 5
//        MSort_Indices[4] = 1    ; from MSort_Values[1] = 9
//


  • Demo GUI
    • Events
      • Player - Player 1 (Red) skips a cinematic sequence
    • Conditions
    • Actions
      • -------- ------------------------------------------------------------------------ --------
      • -------- --------------------- Sort Units by HP ----------------------- --------
      • -------- ------------------------------------------------------------------------ --------
      • -------- Tells Merge Sort to sort in Ascending order --------
      • Set MSort_Ascending = True
      • -------- Pick Every unit --------
      • Custom script: set bj_wantDestroyGroup = true
      • Set TempIndex = 0
      • Unit Group - Pick every unit in (Units in (Playable map area)) and do (Actions)
        • Loop - Actions
          • -------- Increment the Index --------
          • Set TempIndex = (TempIndex + 1)
          • -------- Store the Unit to an array --------
          • Set TempUnitArray[TempIndex] = (Picked unit)
          • -------- Store the value to be compared in MSort_Values --------
          • Set MSort_Values[TempIndex] = (Life of (Picked unit))
          • -------- IMPORTANT: Initialize the Indices --------
          • Set MSort_IndexInitial[TempIndex] = TempIndex
      • -------- Run the Trigger to Sort the Values --------
      • Set MSort_StartIndex = 1
      • Set MSort_EndIndex = TempIndex
      • Trigger - Run Merge Sort <gen> (checking conditions)
      • -------- MSort_Indices now contains the sorted indices --------
      • For each (Integer TempIndex) from MSort_StartIndex to MSort_EndIndex, do (Actions)
        • Loop - Actions
          • -------- TempUnitArray[ MSort_Indices[1] ] <- 1st Unit --------
          • -------- TempUnitArray[ MSort_Indices[2] ] <- 2nd Unit --------
          • -------- TempUnitArray[ MSort_Indices[n] ] <- nth Unit --------
          • Set TempLoc = (Position of TempUnitArray[MSort_Indices[TempIndex]])
          • Floating Text - Create floating text that reads (String(TempIndex)) at TempLoc with Z offset 250.00, using font size 25.00, color (100.00%, 100.00%, 100.00%), and 0.00% transparency
          • Set TempFloatingText = (Last created floating text)
          • Floating Text - Change TempFloatingText: Disable permanence
          • Floating Text - Change the lifespan of TempFloatingText to 8.00 seconds
          • Floating Text - Change the fading age of TempFloatingText to 7.00 seconds
          • Floating Text - Show TempFloatingText for (All players)


Changelog:
v1.00 - 7 January 2015
- Initial Release

v1.01 - 8 January 2015
- Slightly changed the algorithm to achieve true O(n logn) at the cost of more instruction for the user.

Keywords:
sort, merge, sorting, order, rank, low to high, high to low, ascending, descending
Contents

Merge Sort (Map)

Reviews
15:48, 8th Jan 2016 IcemanBo: Can be useful. Also very nice GIF provided to show the mechanismn. Demos are good and needed, but a short info "how to use", unrelated to demos, would be useful, tool.

Moderator

M

Moderator

15:48, 8th Jan 2016
IcemanBo:
Can be useful. Also very nice GIF provided to show the mechanismn.
Demos are good and needed, but a short info "how to use", unrelated to demos, would be useful, tool.
 
Level 22
Joined
Feb 6, 2014
Messages
2,468
Edit:
I updated it to achieve true O(n logn)

Edit2:
Just to clarify, in the previous version, this:
  • -------- IMPORTANT: Initialize the Indices --------
  • Set MSort_IndexInitial[TempIndex] = TempIndex
was done automatically so as a result, the system have to loop again. The previous version was still Merge Sort, but had a higher time complexity due to the automatic assigning of IndexInitial. Now, the map maker has to manually do that while assigning MSort_Values but result to greater efficiency since it doesn't have to loop again.
 
Last edited:

Chaosy

Tutorial Reviewer
Level 39
Joined
Jun 9, 2011
Messages
13,083
I don't quite think this is optimal.

I coded this using a formula from wikipedia. The code was much shorter than this one.
In fact I only needed two short loops.

edit:
JASS:
//! zinc
    library test
	{
		public function sortNumbers(integer start, integer end)
		{
			integer i, j, x = 0;
			for(start <= i < end)
			{
				x = udg_A[i];
				j = i;
				while(j > 0 && udg_A[j - 1] > x)
				{
					udg_A[j] = udg_A[j - 1];
					j = j - 1;
				}
				udg_A[j] = x;
			}
			i = start;
			for(start <= i < end)
			{
				BJDebugMsg(I2S(udg_A[i]));
			}
		}
    }

To use it in accending order just loop from the array backwards.
 
Level 17
Joined
Nov 21, 2012
Messages
836
Excellent system! Access to sorted indices is very importand for me.
I'm saving damage dealt by players to enemy, and after sort I can get biggest damage and corresponding player. The same for 2nd, 3rd place.
Besides sorting players, it can be used for sorting units' some value, passing thier custom value as MSort_IndexInitial. 5/5
 
Top