-
Listen to a special audio message from Bill Roper to the Hive Workshop community (Bill is a former Vice President of Blizzard Entertainment, Producer, Designer, Musician, Voice Actor) 🔗Click here to hear his message!
-
Read Evilhog's interview with Gregory Alper, the original composer of the music for WarCraft: Orcs & Humans 🔗Click here to read the full interview.
-
Create a void inspired texture for Warcraft 3 and enter Hive's 34th Texturing Contest: Void! Click here to enter!
-
The Hive's 22nd Icon Contest: Creep Abilities is now concluded, time to vote for your favourite set of icons! Click here to vote!
Merge Sort [GUI Friendly] v1.01
- Author(s)
- Flux
- Tags
- System, GUI / Triggers, JASS
- Size
- 21.75 KB
- Rating
- Downloads
- 152
- Created
- Jan 7, 2016
- Updated
- Jan 8, 2016
- Resources
- 1
- State
Approved
This bundle is marked as recommended. It works and satisfies the submission rules.
Code
JASS:
// Merge Sort [GUI Friendly] v1.01
// by Flux
// https://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
Reviews
- Joined
- Sep 6, 2013
- Messages
- 6,742
Seems to work. Cool. I have wrote QuickSort a while ago, but it's complexity may be worse in some cases as MergeSort.
But maybe we can make a little addition in our code snipptets collection here: https://www.hiveworkshop.com/forums/triggers-scripts-269/small-code-snippets-40758/
Edit: Will recheck my quicksort and maybe post it in linked thread soon.
But maybe we can make a little addition in our code snipptets collection here: https://www.hiveworkshop.com/forums/triggers-scripts-269/small-code-snippets-40758/
Edit: Will recheck my quicksort and maybe post it in linked thread soon.
- Joined
- Feb 6, 2014
- Messages
- 2,466
Edit:
I updated it to achieve true O(n logn)
Edit2:
Just to clarify, in the previous version, this:
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
Last edited:
Chaosy
Tutorial Reviewer
- Joined
- Jun 9, 2011
- Messages
- 13,288
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:
To use it in accending order just loop from the array backwards.
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.
- Joined
- Feb 6, 2014
- Messages
- 2,466
What sorting algorithm is that?
Shorter codes != better algorithm. Just look at Bubble Sort for example.
By the way, here's the result of the comparison of some sorting algorithm
Sort Comparison
Shorter codes != better algorithm. Just look at Bubble Sort for example.
By the way, here's the result of the comparison of some sorting algorithm
Sort Comparison
Chaosy
Tutorial Reviewer
- Joined
- Jun 9, 2011
- Messages
- 13,288
- Joined
- Nov 21, 2012
- Messages
- 835
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
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
- Joined
- Dec 13, 2018
- Messages
- 2,384
Acolyte of Life
Can someone translate this to Lua?
