mirror of
https://github.com/irmen/prog8.git
synced 2025-07-08 03:24:07 +00:00
e8795859c5
added sorting routines that sort a values array together with the keys array optimized gnomesort a little
104 lines
3.5 KiB
Lua
104 lines
3.5 KiB
Lua
; **experimental** data sorting routines, API subject to change!!
|
|
|
|
; NOTE: gnomesort is not implemented here, just use shellshort.
|
|
|
|
sorting {
|
|
%option ignore_unused
|
|
|
|
sub shellsort_ub(uword @requirezp values, ubyte num_elements) {
|
|
num_elements--
|
|
ubyte @zp gap
|
|
for gap in [132, 57, 23, 10, 4, 1] {
|
|
ubyte i
|
|
for i in gap to num_elements {
|
|
ubyte @zp temp = values[i]
|
|
ubyte @zp j = i
|
|
ubyte @zp k = j-gap
|
|
repeat {
|
|
ubyte @zp v = values[k]
|
|
if v <= temp break
|
|
if j < gap break
|
|
values[j] = v
|
|
j = k
|
|
k -= gap
|
|
}
|
|
values[j] = temp
|
|
}
|
|
}
|
|
}
|
|
|
|
sub shellsort_uw(uword @requirezp values, ubyte num_elements) {
|
|
num_elements--
|
|
ubyte gap
|
|
for gap in [132, 57, 23, 10, 4, 1] {
|
|
ubyte i
|
|
for i in gap to num_elements {
|
|
uword @zp temp = peekw(values+i*$0002)
|
|
ubyte @zp j = i
|
|
ubyte @zp k = j-gap
|
|
while j>=gap {
|
|
uword @zp v = peekw(values+k*2)
|
|
if v <= temp break
|
|
pokew(values+j*2, v)
|
|
j = k
|
|
k -= gap
|
|
}
|
|
pokew(values+j*2, temp)
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
sub shellsort_by_ub(uword @requirezp ub_keys, uword @requirezp wordvalues, ubyte num_elements) {
|
|
; sorts the 'wordvalues' array (no-split array of words) according to the 'ub_keys' array (which also gets sorted ofcourse).
|
|
num_elements--
|
|
ubyte @zp gap
|
|
for gap in [132, 57, 23, 10, 4, 1] {
|
|
ubyte i
|
|
for i in gap to num_elements {
|
|
ubyte @zp temp = ub_keys[i]
|
|
uword temp_wv = peekw(wordvalues + i*$0002)
|
|
ubyte @zp j = i
|
|
ubyte @zp k = j-gap
|
|
repeat {
|
|
ubyte @zp v = ub_keys[k]
|
|
if v <= temp break
|
|
if j < gap break
|
|
ub_keys[j] = v
|
|
pokew(wordvalues + j*$0002, peekw(wordvalues + k*$0002))
|
|
j = k
|
|
k -= gap
|
|
}
|
|
ub_keys[j] = temp
|
|
pokew(wordvalues + j*$0002, temp_wv)
|
|
}
|
|
}
|
|
}
|
|
|
|
sub shellsort_by_uw(uword @requirezp uw_keys, uword @requirezp wordvalues, ubyte num_elements) {
|
|
; sorts the 'wordvalues' array according to the 'uw_keys' array (which also gets sorted ofcourse).
|
|
; both arrays should be no-split array of words. uw_keys are unsigned.
|
|
num_elements--
|
|
ubyte gap
|
|
for gap in [132, 57, 23, 10, 4, 1] {
|
|
ubyte i
|
|
for i in gap to num_elements {
|
|
uword @zp temp = peekw(uw_keys+i*$0002)
|
|
uword temp_wv = peekw(wordvalues + i*$0002)
|
|
ubyte @zp j = i
|
|
ubyte @zp k = j-gap
|
|
while j>=gap {
|
|
uword @zp v = peekw(uw_keys+k*2)
|
|
if v <= temp break
|
|
pokew(uw_keys+j*2, v)
|
|
pokew(wordvalues + j*$0002, peekw(wordvalues + k*$0002))
|
|
j = k
|
|
k -= gap
|
|
}
|
|
pokew(uw_keys+j*2, temp)
|
|
pokew(wordvalues + j*$0002, temp_wv)
|
|
}
|
|
}
|
|
}
|
|
}
|