Open Forum > What's New

Array Sort

(1/1)

Support:
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 File

--- Code: Script BASIC ---MODULE 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                                                                        
Example Use

--- Code: Script BASIC ---' 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 
Output

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)


--- Code: Script BASIC ---' Script BASIC Array Sort IMPORT t.bas OPEN "bible.txt" FOR INPUT AS #1s = 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 
Output

--- Code: ---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$

--- End code ---

The array sort routine also works with associative arrays and isn't restricted to a single indies array.


--- Code: Script BASIC ---' 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$

Navigation

[0] Message Index