One feature I have always wanted to add to Script BASIC was an
array sort function. My first thought was to add the function to the existing
T (Tools) extension module. This extension module already contains a wealth of string / array functions written in
C. I took a peek at the C
qsort function and the source to the GNU sort command line utility.
I decided on prototyping the array sort routine in Script BASIC first before committing to a direction. As it turns out my
merge sort effort satisfies my immediate requirements for an array sort function and I added it to the
T include.
Note: Duplicates are returned in the result array as one instance.
(T)ools Include FileMODULE T
DECLARE SUB ::md5 ALIAS "md5fun" LIB "t"
DECLARE COMMAND ::ArrayToString ALIAS "serialize" LIB "t"
DECLARE COMMAND ::ArrayToXML ALIAS "xmlserialize" LIB "t"
DECLARE SUB ::StringToArray ALIAS "unserialize" LIB "t"
DECLARE COMMAND ::Array2String ALIAS "serialize" LIB "t"
DECLARE COMMAND ::Array2XML ALIAS "xmlserialize" LIB "t"
DECLARE SUB ::String2Array ALIAS "unserialize" LIB "t"
DECLARE COMMAND ::ArrayToStringMD5 ALIAS "md5serialize" LIB "t"
DECLARE SUB ::StringToArrayMD5 ALIAS "md5unserialize" LIB "t"
DECLARE COMMAND ::Array2StringMD5 ALIAS "md5serialize" LIB "t"
DECLARE SUB ::String2ArrayMD5 ALIAS "md5unserialize" LIB "t"
DECLARE SUB ::SaveString ALIAS "savestring" LIB "t"
DECLARE SUB ::LoadString ALIAS "loadstring" LIB "t"
DECLARE SUB ::Exit ALIAS "toolExit" LIB "t"
SUB merge(left_side, right_side, result)
LOCAL left_size, left_ptr, right_size, right_ptr, result_ptr
left_size = UBOUND(left_side)
left_ptr = 0
right_size = UBOUND(right_side)
right_ptr = 0
result_ptr = 0
WHILE left_ptr <= left_size AND right_ptr <= right_size
IF left_side[left_ptr] <= right_side[right_ptr] THEN
result[result_ptr] = left_side[left_ptr]
left_ptr += 1
result_ptr += 1
ELSE
result[result_ptr] = right_side[right_ptr]
right_ptr += 1
result_ptr += 1
END IF
WEND
WHILE left_ptr <= left_size
result[result_ptr] = left_side[left_ptr]
left_ptr += 1
result_ptr += 1
WEND
WHILE right_ptr <= right_size
result[result_ptr] = right_side[right_ptr]
right_ptr += 1
result_ptr += 1
WEND
END SUB
SUB sort(unsorted)
LOCAL left_side, right_side, the_middle, array_size, result, x, y, z
array_size = UBOUND(unsorted)
IF array_size = 0 THEN
EXIT SUB
END IF
the_middle = FIX((array_size + 1) / 2)
y = 0
FOR x = 0 TO the_middle - 1
left_side[y] = unsorted[x]
y += 1
NEXT
z = 0
FOR x = the_middle TO array_size
right_side[z] = unsorted[x]
z += 1
NEXT
sort(left_side)
sort(right_side)
merge(left_side, right_side, result)
unsorted = result
END SUB
END MODULE
' Script BASIC Array Sort
IMPORT t.bas
s = "pear,cranberry,orange,apple,carrot,banana,grape"
SPLITA s BY "," TO a
t::sort(a)
FOR x = 0 TO UBOUND(a)
PRINT a[x],"\n"
NEXT
jrs@laptop:~/sb/sb22/test$ time scriba sort.sb
apple
banana
carrot
cranberry
grape
orange
pear
real 0m0.008s
user 0m0.007s
sys 0m0.000s
jrs@laptop:~/sb/sb22/test$
As a stress test, I thought I would sort each line in a text version of the Bible. (30383 lines / 4,047,392 bytes)
' Script BASIC Array Sort
IMPORT t.bas
OPEN "bible.txt" FOR INPUT AS #1
s = INPUT(LOF(1),1)
SPLITA s BY "\n" TO a
t::sort(a)
FOR x = UBOUND(a) - 10 TO UBOUND(a)
PRINT a[x],"\n"
NEXT
jrs@laptop:~/sb/sb22/test$ time scriba sort.sb
Zebulun and Naphtali were a people that jeoparded their lives unto the death in the high places of the field.
Zebulun shall dwell at the haven of the sea; and he shall be for an haven of ships; and his border shall be unto Zidon.
Zedekiah was one and twenty years old when he began to reign, and he reigned eleven years in Jerusalem. And his mother's name was Hamutal the daughter of Jeremiah of Libnah.
Zedekiah was one and twenty years old when he began to reign, and reigned eleven years in Jerusalem.
Zelek the Ammonite, Naharai the Berothite, the armourbearer of Joab the son of Zeruiah,
Zelek the Ammonite, Nahari the Beerothite, armourbearer to Joab the son of Zeruiah,
Zenan, and Hadashah, and Migdalgad,
Zion heard, and was glad; and the daughters of Judah rejoiced because of thy judgments, O LORD.
Zion shall be redeemed with judgment, and her converts with righteousness.
Zion spreadeth forth her hands, and there is none to comfort her: the LORD hath commanded concerning Jacob, that his adversaries should be round about him: Jerusalem is as a menstruous woman among them.
Ziph, and Telem, and Bealoth,
real 0m13.069s
user 0m12.173s
sys 0m0.810s
jrs@laptop:~/sb/sb22/test$
The array sort routine also works with associative arrays and isn't restricted to a single indies array.
' Script BASIC Array Sort
IMPORT t.bas
s = "pear,apple,cranberry,orange,carrot,banana,grape"
SPLITA s BY "," TO a{"food"}
t::sort(a{"food"})
FOR x = 0 TO UBOUND(a{"food"})
PRINT a{"food"}[x],"\n"
NEXT
jrs@laptop:~/sb/sb22/test$ scriba arraysort.sb
apple
banana
carrot
cranberry
grape
orange
pear
jrs@laptop:~/sb/sb22/test$
Show Posts
