- Joined
- Feb 6, 2014
- Messages
- 2,466
Haven't seen any sorting algorithms here so I made one.
****** EDIT: ******
My googling skill needs some polish
I just found out this exist
http://www.hiveworkshop.com/forums/jass-resources-412/snippet-mergesort-206213/index2.html
Meh, I'll just make a GUI version instead..
**********************
*Waiting for constructive criticism....
EDIT:
* Forgot to remove
* Ignore
****** EDIT: ******
My googling skill needs some polish
I just found out this exist
http://www.hiveworkshop.com/forums/jass-resources-412/snippet-mergesort-206213/index2.html
Meh, I'll just make a GUI version instead..
**********************
JASS:
library MergeSort
/*
by Flux
[url]http://www.hiveworkshop.com/forums/members/flux/[/url]
MergeSort sorts an array in ascending or
in descending order (based on configuration).
Unlike other simple sorting algorithms, MergeSort
has a worst case performance of O(n logn) which
makes the algorithm efficient.
*/
//! novjass
***************** API: *******************
- function MergeSort takes integer startingIndex, integer endingIndex returns nothing
Merge Sort the values of mergeSortValues from startingIndex to endingIndex
- function MergeSortAscending takes boolean flag returns nothing
Sets the sorting order
************* HOW TO USE: *********(******
1. Store your values in mergeSortValues[0 to n]
2. call MergeSortAscending(flag) to set the sorting order
2. call MergeSort(0, n)
3. mergeSortValues[0 to n] is now sorted!
//! endnovjass
globals
integer array mergeSortValues
private integer array left
private integer array right
private boolean ascending
endglobals
private function Merge takes integer leftStart, integer leftEnd, integer rightStart, integer rightEnd returns nothing
local integer nL = leftEnd + 1
local integer nR = rightEnd + 1
local integer i = leftStart
local integer j = rightStart
local integer k = i
loop
exitwhen i == nL or j == nR
if ascending then
if left[i] < right[j] then
set mergeSortValues[k] = left[i]
set k = k + 1
set i = i + 1
else
set mergeSortValues[k] = right[j]
set k = k + 1
set j = j + 1
endif
else
if left[i] > right[j] then
set mergeSortValues[k] = left[i]
set k = k + 1
set i = i + 1
else
set mergeSortValues[k] = right[j]
set k = k + 1
set j = j + 1
endif
endif
endloop
//Fill up remaining
loop
exitwhen i == nL
set mergeSortValues[k] = left[i]
set k = k + 1
set i = i + 1
endloop
loop
exitwhen j == nR
set mergeSortValues[k] = right[j]
set k = k + 1
set j = j + 1
endloop
endfunction
private function Update takes integer start, integer mid, integer end returns nothing
local integer i = start
loop
exitwhen i > mid
set left[i] = mergeSortValues[i]
set i = i + 1
endloop
loop
exitwhen i > end
set right[i] = mergeSortValues[i]
set i = i + 1
endloop
endfunction
function MergeSort takes integer start, integer end returns nothing
local integer i = start
local integer mid = (end + start)/2
local integer id = GetRandomInt(1, 1000)
if end - start >= 1 then
call Update(start, mid, end)
call MergeSort(start, mid)
call MergeSort(mid+1, end)
call Update(start, mid, end)
call Merge(start, mid, mid+1, end)
endif
endfunction
function MergeSortAscending takes boolean flag returns nothing
set ascending = flag
endfunction
endlibrary
JASS:
scope Test initializer OnInit
globals
private integer array unsorted
endglobals
private function Test takes nothing returns nothing
local integer i = 0
//Transfer the unsorted array to mergeSortValues array
call BJDebugMsg("Unsorted List:")
loop
exitwhen i > 9
set mergeSortValues[i] = unsorted[i]
//Display the unsorted list
call BJDebugMsg("mergeSortValues[" + I2S(i) + "] = " + I2S(mergeSortValues[i]))
set i = i + 1
endloop
//Tells the system to sort in ascending order
call MergeSortAscending(true)
//This function will sort mergeSortValues
//Sort the array from index 0 to index 4
call MergeSort(0, 9)
//Display the sorted array
set i = 0
call BJDebugMsg("Sorted List:")
loop
exitwhen i > 9
call BJDebugMsg("mergeSortValues[" + I2S(i) + "] = " + I2S(mergeSortValues[i]))
set i = i + 1
endloop
endfunction
//Create A delay so that is is stored in Message Log
private function OnInit takes nothing returns nothing
call TimerStart(CreateTimer(), 0.4, false, function Test)
//Initialize unsorted array
//You have an unsorted array
set unsorted[0] = 7
set unsorted[1] = 49
set unsorted[2] = 28
set unsorted[3] = 1
set unsorted[4] = 14
set unsorted[5] = 4
set unsorted[6] = 10
set unsorted[7] = 4
set unsorted[8] = 32
set unsorted[9] = 53
endfunction
endscope*Waiting for constructive criticism....
EDIT:
* Forgot to remove
local integer id = GetRandomInt(1, 1000) that was used for debugging purposes.* Ignore
//Sort the array from index 0 to index 4.Attachments
Last edited:
).
