- Joined
- Apr 24, 2012
- Messages
- 5,113
Work In Progress
Because, why not?
probably, going to extend the Table struct.
all codes will be based from :
http://rosettacode.org/wiki/Category:Sorting_Algorithms
Note: all sorting algorithms will be non-recursive.
Because, why not?
probably, going to extend the Table struct.
JASS:
library TableSort/*
*************************************************************************************
*
* Table sorting algorithms
*
* Sorting algorithms include:
* - gnome sort
* - insertion sort
* - cycle sort
* - shell sort
* - comb sort
* - bubble sort
* - cocktail sort
* - quick sort
* - merge sort
* - heap sort
*
*************************************************************************************
*
* */ requires /*
*
* */ Table /*
*
*************************************************************************************
*
* API
*
* TableSort(myTable).<real or int>.<name of sorting method>(startIndex, endIndex, ascending)
*
* <StructName>Sort.<name of sorting method>(startIndex, endIndex, ascending)
*************************************************************************************/
private function Real2S takes real r returns string
return R2S(r)
endfunction
private function Int2S takes integer r returns string
return I2S(r)
endfunction
//! textmacro TABLE_SORT takes STRUCT, KEY, TYPE
struct $STRUCT$Sort extends array
method print takes string tname, integer start, integer end returns nothing
local string s = tname + " = [ "
local integer i = start
local Table t = table
loop
set s = s + $STRUCT$2S(t$KEY$[i])
set i = i + 1
exitwhen i > end
set s = s + ", "
endloop
set s = s + " ]"
//call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 30, s)
call Log.write(s)
endmethod
method operator table takes nothing returns Table
return Table(this)
endmethod
method sorted takes integer start, integer end, boolean asc returns boolean
local Table t = table
loop
exitwhen start > end
if (asc and t$KEY$[start] < t$KEY$[start + 1]) != (not asc and t$KEY$[start] > t$KEY$[start + 1]) then
return false
endif
set start = start + 1
endloop
return true
endmethod
private method swap takes integer j, integer k returns nothing
local $TYPE$ temp = table$KEY$[j]
set table$KEY$[j] = table$KEY$[k]
set table$KEY$[k] = temp
endmethod
method gnome takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer i = start + 1
local integer pos
loop
exitwhen i > end
if sorted(start, end, asc) then
return
endif
set pos = i
loop
exitwhen pos <= start or ((asc and t$KEY$[pos - 1] < t$KEY$[pos]) != (not asc and t$KEY$[pos - 1] > t$KEY$[pos]))
call swap(pos - 1, pos)
set pos = pos - 1
endloop
set i = i + 1
debug call print("t", start, end)
endloop
endmethod
method insertion takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer i = start + 1
local integer pos
local $TYPE$ value
loop
exitwhen i > end
if sorted(start, end, asc) then
return
endif
set value = t$KEY$[i]
set pos = i - 1
loop
exitwhen not (pos >= start and ((asc and t$KEY$[pos] > value) != (not asc and t$KEY$[pos] < value)))
set t$KEY$[pos + 1] = t$KEY$[pos]
set pos = pos - 1
endloop
set t$KEY$[pos + 1] = value
set i = i + 1
debug call print("t", start, end)
endloop
endmethod
method cycle takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer cs = start
local integer pos
local integer i
local $TYPE$ val
local $TYPE$ tmp
loop
exitwhen cs >= end
if sorted(start, end, asc) then
return
endif
set val = t$KEY$[cs]
set pos = cs
set i = cs
loop
exitwhen i > end
if (asc and t$KEY$[i] < val) != (not asc and t$KEY$[i] > val) then
set pos = pos + 1
endif
set i = i + 1
endloop
if pos != cs then
loop
exitwhen val != t$KEY$[pos]
set pos = pos + 1
endloop
set tmp = t$KEY$[pos]
set t$KEY$[pos] = val
set val = tmp
loop
exitwhen pos == cs
set pos = cs
set i = cs + 1
loop
exitwhen i > end
if (asc and t$KEY$[i] < val) != (not asc and t$KEY$[i] > val) then
set pos = pos + 1
endif
set i = i + 1
endloop
loop
exitwhen val != t$KEY$[pos]
set pos = pos + 1
endloop
set tmp = t$KEY$[pos]
set t$KEY$[pos] = val
set val = tmp
endloop
endif
set cs = cs + 1
endloop
endmethod
method shell takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer inc = (end - start)/2
local $TYPE$ temp
local integer i
local integer j
loop
exitwhen inc <= 0
if sorted(start, end, asc) then
return
endif
set i = start + inc
loop
exitwhen i > (end - start)
set temp = t$KEY$[i]
set j = i
loop
exitwhen not (j >= start + inc and ((asc and t$KEY$[j - inc] > temp) != (not asc and t$KEY$[j - inc] < temp)))
set t$KEY$[j] = t$KEY$[j - inc]
set j = j - inc
endloop
set t$KEY$[j] = temp
set i = i + 1
endloop
set inc = R2I(0.5 + I2R(inc)/2.2)
debug call print("t", start, end)
endloop
endmethod
method comb takes integer start, integer end, boolean asc returns nothing
local integer gap = end - start
local integer swaps = 0
local integer k
local Table t = table
loop
exitwhen gap + swaps <= 1
if sorted(start, end, asc) then
return
endif
set swaps = 0
if gap > 1 then
set gap = R2I(I2R(gap)/1.2473)
endif
set k = start
loop
exitwhen k > (end - gap)
if (asc and t$KEY$[k] > t$KEY$[k + gap]) != (not asc and t$KEY$[k] < t$KEY$[k + gap]) then
call swap(k, k + gap)
set swaps = swaps + 1
endif
set k = k + 1
endloop
debug call print("t", start, end)
endloop
endmethod
method bubble takes integer start, integer end, boolean asc returns nothing
local boolean swapped
local integer i
debug local integer e = end
local Table t = table
loop
set swapped = false
set i = start
loop
if (asc and t$KEY$[i] > t$KEY$[i + 1]) != (not asc and t$KEY$[i] < t$KEY$[i + 1]) then
call swap(i, i + 1)
set swapped = true
endif
exitwhen i == end - 1
set i = i + 1
endloop
set end = end - 1
exitwhen not swapped
debug call print("t", start, e)
endloop
endmethod
method cocktail takes integer start, integer end, boolean asc returns nothing
local boolean swapped
local integer i
local Table t = table
loop
set swapped = false
set i = start
loop
if (asc and t$KEY$[i] > t$KEY$[i + 1]) != (not asc and t$KEY$[i] < t$KEY$[i + 1]) then
call swap(i, i + 1)
set swapped = true
endif
exitwhen i == end - 1
set i = i + 1
endloop
exitwhen not swapped
set swapped = false
set i = end - 1
loop
if (asc and t$KEY$[i] > t$KEY$[i + 1]) != (not asc and t$KEY$[i] < t$KEY$[i + 1]) then
call swap(i, i + 1)
set swapped = true
endif
exitwhen i == start
set i = i - 1
endloop
debug call print("t", start, end)
endloop
endmethod
private method qpartition takes integer start, integer end, boolean asc returns integer
local Table t = table
local $TYPE$ x = t$KEY$[end]
local integer i = start
local integer j = i
loop
exitwhen j > end
if (asc and t$KEY$[j] < x) != (not asc and t$KEY$[j] > x) then
call swap(i, j)
set i = i + 1
endif
set j = j + 1
endloop
call swap(i, end)
return i
endmethod
method quick takes integer start, integer end, boolean asc returns nothing
local Table qstack = Table.create()
local integer top = -1
local integer p
local integer s
local integer e
set top = top + 1
set qstack[top] = start
set top = top + 1
set qstack[top] = end
loop
exitwhen top == -1
set e = qstack[top]
set top = top - 1
set s = qstack[top]
set top = top - 1
if sorted(start, end, asc) then
call qstack.destroy()
return
endif
set p = qpartition(s, e, asc)
if p - 1 > s then
set top = top + 1
set qstack[top] = s
set top = top + 1
set qstack[top] = p - 1
endif
if p + 1 < e then
set top = top + 1
set qstack[top] = p + 1
set top = top + 1
set qstack[top] = e
endif
debug call print("t", start, end)
endloop
call qstack.destroy()
endmethod
private method mergeValue takes integer l, integer le, integer r, integer re, boolean asc returns nothing
local Table t = table
local integer i = l
local integer j = r
local integer k = 0
local Table left = Table.create()
local Table right = Table.create()
loop
exitwhen i > le
set left$KEY$[i] = t$KEY$[i]
set i = i + 1
endloop
loop
exitwhen j > re
set right$KEY$[j] = t$KEY$[j]
set j = j + 1
endloop
set i = l
set j = r
set k = l
loop
exitwhen i > le or j > re
if (asc and left$KEY$[i] < right$KEY$[j]) != (not asc and left$KEY$[i] > right$KEY$[j]) then
set t$KEY$[k] = left$KEY$[i]
set i = i + 1
else
set t$KEY$[k] = right$KEY$[j]
set j = j + 1
endif
set k = k + 1
endloop
loop
exitwhen i > le
set t$KEY$[k] = left$KEY$[i]
set i = i + 1
set k = k + 1
endloop
loop
exitwhen j > re
set t$KEY$[k] = right$KEY$[j]
set j = j + 1
set k = k + 1
endloop
call left.destroy()
call right.destroy()
endmethod
method merge takes integer start, integer end, boolean asc returns nothing
local Table stack = Table.create()
local integer top = -1
local integer m = 0
local integer s
local integer e
set top = top + 1
set stack[top] = start
set top = top + 1
set stack[top] = end
loop
exitwhen top < 0
set e = stack[top]
set top = top - 1
set s = stack[top]
set top = top - 1
if sorted(start, end, asc) then
return
endif
if (e - s) > 0 then
set m = (s + e)/2
set top = top + 1
set stack[top] = s
set top = top + 1
set stack[top] = m
set top = top + 1
set stack[top] = m + 1
set top = top + 1
set stack[top] = e
call mergeValue(s, m, m + 1, e, asc)
endif
debug call print("t", start, end)
endloop
call stack.destroy()
endmethod
private method siftDown takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer root = start
local integer child
loop
set child = root*2 + 1
exitwhen child > end
if child + 1 <= end and ((asc and t$KEY$[child] < t$KEY$[child + 1]) != (not asc and t$KEY$[child] > t$KEY$[child + 1])) then
set child = child + 1
endif
if ((asc and t$KEY$[root] < t$KEY$[child]) != (not asc and t$KEY$[root] > t$KEY$[child])) then
call swap(root, child)
set root = child
else
return
endif
endloop
endmethod
method heap takes integer start, integer end, boolean asc returns nothing
local integer s = (end + start)/2
local integer e = end
loop
exitwhen s < start
if sorted(start, end, asc) then
return
endif
call siftDown(s, end, asc)
set s = s - 1
debug call print("t", start, end)
endloop
loop
exitwhen e <= start
if sorted(start, end, asc) then
return
endif
call swap(start, e)
call siftDown(start, e - 1, asc)
set e = e - 1
debug call print("t", start, end)
endloop
endmethod
endstruct
//! endtextmacro
//! runtextmacro TABLE_SORT("Int", ".integer", "integer")
//! runtextmacro TABLE_SORT("Real", ".real", "real")
struct TableSort extends array
method operator real takes nothing returns RealSort
return this
endmethod
method operator int takes nothing returns IntSort
return this
endmethod
endstruct
//! textmacro STRUCT_SORT takes STRUCT
struct $STRUCT$Sort extends array
method operator table takes nothing returns Table
return Table(this)
endmethod
private method swap takes integer j, integer k returns nothing
local integer temp = table.integer[j]
set table.integer[j] = table.integer[k]
set table.integer[k] = temp
endmethod
method gnome takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer i = start + 1
local integer pos
loop
exitwhen i > end
set pos = i
loop
exitwhen pos <= start or ((asc and $STRUCT$(t.integer[pos - 1]) < $STRUCT$(t.integer[pos])) != (not asc and $STRUCT$(t.integer[pos - 1]) > $STRUCT$(t.integer[pos])))
call swap(pos - 1, pos)
set pos = pos - 1
endloop
set i = i + 1
endloop
endmethod
method insertion takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer i = start + 1
local integer pos
local $STRUCT$ value
loop
exitwhen i > end
set value = $STRUCT$(t.integer[i])
set pos = i - 1
loop
exitwhen not (pos >= start and ((asc and $STRUCT$(t.integer[pos]) > value) != (not asc and $STRUCT$(t.integer[pos]) < value)))
set t.integer[pos + 1] = t.integer[pos]
set pos = pos - 1
endloop
set t.integer[pos + 1] = value
set i = i + 1
endloop
endmethod
method cycle takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer cs = start
local integer pos
local integer i
local $STRUCT$ val
local $STRUCT$ tmp
loop
exitwhen cs >= end
set val = $STRUCT$(t.integer[cs])
set pos = cs
set i = cs
loop
exitwhen i > end
if (asc and $STRUCT$(t.integer[i]) < val) != (not asc and $STRUCT$(t.integer[i]) > val) then
set pos = pos + 1
endif
set i = i + 1
endloop
if pos != cs then
loop
exitwhen val != $STRUCT$(t.integer[pos])
set pos = pos + 1
endloop
set tmp = $STRUCT$(t.integer[pos])
set t.integer[pos] = val
set val = tmp
loop
exitwhen pos == cs
set pos = cs
set i = cs + 1
loop
exitwhen i > end
if (asc and $STRUCT$(t.integer[i]) < val) != (not asc and $STRUCT$(t.integer[i]) > val) then
set pos = pos + 1
endif
set i = i + 1
endloop
loop
exitwhen val != $STRUCT$(t.integer[pos])
set pos = pos + 1
endloop
set tmp = $STRUCT$(t.integer[pos])
set t.integer[pos] = val
set val = tmp
endloop
endif
set cs = cs + 1
endloop
endmethod
method shell takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer inc = (end - start)/2
local $STRUCT$ temp
local integer i
local integer j
loop
exitwhen inc <= 0
set i = start + inc
loop
exitwhen i > (end - start)
set temp = $STRUCT$(t.integer[i])
set j = i
loop
exitwhen not (j >= start + inc and ((asc and $STRUCT$(t.integer[j - inc]) > temp) != (not asc and $STRUCT$(t.integer[j - inc]) < temp)))
set t.integer[j] = t.integer[j - inc]
set j = j - inc
endloop
set t.integer[j] = temp
set i = i + 1
endloop
set inc = R2I(0.5 + I2R(inc)/2.2)
endloop
endmethod
method comb takes integer start, integer end, boolean asc returns nothing
local integer gap = end - start
local integer swaps = 0
local integer k
local Table t = table
loop
exitwhen gap + swaps <= 1
set swaps = 0
if gap > 1 then
set gap = R2I(I2R(gap)/1.2473)
endif
set k = start
loop
exitwhen k > (end - gap)
if (asc and $STRUCT$(t.integer[k]) > $STRUCT$(t.integer[k + gap])) != (not asc and $STRUCT$(t.integer[k]) < $STRUCT$(t.integer[k + gap])) then
call swap(k, k + gap)
set swaps = swaps + 1
endif
set k = k + 1
endloop
endloop
endmethod
method bubble takes integer start, integer end, boolean asc returns nothing
local boolean swapped
local integer i
debug local integer e = end
local Table t = table
loop
set swapped = false
set i = start
loop
if (asc and $STRUCT$(t.integer[i]) > $STRUCT$(t.integer[i + 1])) != (not asc and $STRUCT$(t.integer[i]) < $STRUCT$(t.integer[i + 1])) then
call swap(i, i + 1)
set swapped = true
endif
exitwhen i == end - 1
set i = i + 1
endloop
set end = end - 1
exitwhen not swapped
endloop
endmethod
method cocktail takes integer start, integer end, boolean asc returns nothing
local boolean swapped
local integer i
local Table t = table
loop
set swapped = false
set i = start
loop
if (asc and $STRUCT$(t.integer[i]) > $STRUCT$(t.integer[i + 1])) != (not asc and $STRUCT$(t.integer[i]) < $STRUCT$(t.integer[i + 1])) then
call swap(i, i + 1)
set swapped = true
endif
exitwhen i == end - 1
set i = i + 1
endloop
exitwhen not swapped
set swapped = false
set i = end - 1
loop
if (asc and $STRUCT$(t.integer[i]) > $STRUCT$(t.integer[i + 1])) != (not asc and $STRUCT$(t.integer[i]) < $STRUCT$(t.integer[i + 1])) then
call swap(i, i + 1)
set swapped = true
endif
exitwhen i == start
set i = i - 1
endloop
endloop
endmethod
private method qpartition takes integer start, integer end, boolean asc returns integer
local Table t = table
local $STRUCT$ x = $STRUCT$(t.integer[end])
local integer i = start
local integer j = i
loop
exitwhen j > end
if (asc and $STRUCT$(t.integer[j]) < x) != (not asc and $STRUCT$(t.integer[j]) > x) then
call swap(i, j)
set i = i + 1
endif
set j = j + 1
endloop
call swap(i, end)
return i
endmethod
method quick takes integer start, integer end, boolean asc returns nothing
local Table qstack = Table.create()
local integer top = -1
local integer p
local integer s
local integer e
set top = top + 1
set qstack[top] = start
set top = top + 1
set qstack[top] = end
loop
exitwhen top == -1
set e = qstack[top]
set top = top - 1
set s = qstack[top]
set top = top - 1
set p = qpartition(s, e, asc)
if p - 1 > s then
set top = top + 1
set qstack[top] = s
set top = top + 1
set qstack[top] = p - 1
endif
if p + 1 < e then
set top = top + 1
set qstack[top] = p + 1
set top = top + 1
set qstack[top] = e
endif
endloop
call qstack.destroy()
endmethod
private method mergeValue takes integer l, integer le, integer r, integer re, boolean asc returns nothing
local Table t = table
local integer i = l
local integer j = r
local integer k = 0
local Table left = Table.create()
local Table right = Table.create()
loop
exitwhen i > le
set left.integer[i] = t.integer[i]
set i = i + 1
endloop
loop
exitwhen j > re
set right.integer[j] = t.integer[j]
set j = j + 1
endloop
set i = l
set j = r
set k = l
loop
exitwhen i > le or j > re
if (asc and $STRUCT$(left.integer[i]) < $STRUCT$(right.integer[j])) != (not asc and $STRUCT$(left.integer[i]) > $STRUCT$(right.integer[j])) then
set t.integer[k] = left.integer[i]
set i = i + 1
else
set t.integer[k] = right.integer[j]
set j = j + 1
endif
set k = k + 1
endloop
loop
exitwhen i > le
set t.integer[k] = left.integer[i]
set i = i + 1
set k = k + 1
endloop
loop
exitwhen j > re
set t.integer[k] = right.integer[j]
set j = j + 1
set k = k + 1
endloop
call left.destroy()
call right.destroy()
endmethod
method merge takes integer start, integer end, boolean asc returns nothing
local Table stack = Table.create()
local integer top = -1
local integer m = 0
local integer s
local integer e
set top = top + 1
set stack[top] = start
set top = top + 1
set stack[top] = end
loop
exitwhen top < 0
set e = stack[top]
set top = top - 1
set s = stack[top]
set top = top - 1
if (e - s) > 0 then
set m = (s + e)/2
set top = top + 1
set stack[top] = s
set top = top + 1
set stack[top] = m
set top = top + 1
set stack[top] = m + 1
set top = top + 1
set stack[top] = e
call mergeValue(s, m, m + 1, e, asc)
endif
endloop
call stack.destroy()
endmethod
private method siftDown takes integer start, integer end, boolean asc returns nothing
local Table t = table
local integer root = start
local integer child
loop
set child = root*2 + 1
exitwhen child > end
if child + 1 <= end and ((asc and $STRUCT$(t.integer[child]) < $STRUCT$(t.integer[child + 1])) != (not asc and $STRUCT$(t.integer[child]) > $STRUCT$(t.integer[child + 1]))) then
set child = child + 1
endif
if ((asc and $STRUCT$(t.integer[root]) < $STRUCT$(t.integer[child])) != (not asc and $STRUCT$(t.integer[root]) > $STRUCT$(t.integer[child]))) then
call swap(root, child)
set root = child
else
return
endif
endloop
endmethod
method heap takes integer start, integer end, boolean asc returns nothing
local integer s = (end + start)/2
local integer e = end
loop
exitwhen s < start
call siftDown(s, end, asc)
set s = s - 1
endloop
loop
exitwhen e <= start
call swap(start, e)
call siftDown(start, e - 1, asc)
set e = e - 1
endloop
endmethod
endstruct
//! endtextmacro
endlibraryall codes will be based from :
http://rosettacode.org/wiki/Category:Sorting_Algorithms
Note: all sorting algorithms will be non-recursive.
Last edited:
