Array Sort

[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

1. MODULE T                                                                        
2.                                                                                  
3. DECLARE SUB     ::md5              ALIAS "md5fun"         LIB "t"                
4. DECLARE COMMAND ::ArrayToString    ALIAS "serialize"      LIB "t"                
5. DECLARE COMMAND ::ArrayToXML       ALIAS "xmlserialize"   LIB "t"                
6. DECLARE SUB     ::StringToArray    ALIAS "unserialize"    LIB "t"                
7. DECLARE COMMAND ::Array2String     ALIAS "serialize"      LIB "t"                
8. DECLARE COMMAND ::Array2XML        ALIAS "xmlserialize"   LIB "t"                
9. DECLARE SUB     ::String2Array     ALIAS "unserialize"    LIB "t"                
10. DECLARE COMMAND ::ArrayToStringMD5 ALIAS "md5serialize"   LIB "t"                
11. DECLARE SUB     ::StringToArrayMD5 ALIAS "md5unserialize" LIB "t"                
12. DECLARE COMMAND ::Array2StringMD5  ALIAS "md5serialize"   LIB "t"                
13. DECLARE SUB     ::String2ArrayMD5  ALIAS "md5unserialize" LIB "t"                
14. DECLARE SUB     ::SaveString       ALIAS "savestring"     LIB "t"                
15. DECLARE SUB     ::LoadString       ALIAS "loadstring"     LIB "t"                
16. DECLARE SUB     ::Exit             ALIAS "toolExit"       LIB "t"                
17.                                                                                  
18. SUB merge(left_side, right_side, result)                                        
19.   LOCAL left_size, left_ptr, right_size, right_ptr, result_ptr                  
20.   left_size = UBOUND(left_side)                                                  
21.   left_ptr = 0                                                                  
22.   right_size = UBOUND(right_side)                                                
23.   right_ptr = 0                                                                  
24.   result_ptr = 0                                                                
25.   WHILE left_ptr <= left_size AND right_ptr <= right_size                        
26.     IF left_side[left_ptr] <= right_side[right_ptr] THEN                        
27.       result[result_ptr] = left_side[left_ptr]                                  
28.       left_ptr += 1                                                              
29.       result_ptr += 1                                                            
30.     ELSE                                                                        
31.       result[result_ptr] = right_side[right_ptr]                                
32.       right_ptr += 1                                                            
33.       result_ptr += 1                                                            
34.     END IF                                                                      
35.   WEND                                                                          
36.   WHILE left_ptr <= left_size                                                    
37.     result[result_ptr] = left_side[left_ptr]                                    
38.     left_ptr += 1                                                                
39.     result_ptr += 1                                                              
40.   WEND                                                                          
41.   WHILE right_ptr <= right_size                                                  
42.     result[result_ptr] = right_side[right_ptr]                                  
43.     right_ptr += 1                                                              
44.     result_ptr += 1                                                              
45.   WEND                                                                          
46. END SUB                                                                          
47.                                                                                  
48. SUB sort(unsorted)                                                              
49.   LOCAL left_side, right_side, the_middle, array_size, result, x, y, z          
50.   array_size = UBOUND(unsorted)                                                  
51.   IF array_size = 0 THEN                                                        
52.     EXIT SUB                                                                
53.   END IF                                                                        
54.   the_middle = FIX((array_size + 1) / 2)                                        
55.   y = 0                                                                          
56.   FOR x = 0 TO the_middle - 1                                                    
57.     left_side[y] = unsorted[x]                                                  
58.     y += 1                                                                      
59.   NEXT                                                                          
60.   z = 0                                                                          
61.   FOR x = the_middle TO array_size                                              
62.     right_side[z] = unsorted[x]                                                  
63.     z += 1                                                                      
64.   NEXT                                                                          
65.   sort(left_side)                                                                
66.   sort(right_side)                                                              
67.   merge(left_side, right_side, result)                                          
68.   unsorted = result                                                              
69. END SUB                                                                          
70.                                                                                  
71. END MODULE                                                                      
72.  

Example Use

Code: Script BASIC

1. ' Script BASIC Array Sort
2.  
3. IMPORT t.bas
4.  
5. s = "pear,cranberry,orange,apple,carrot,banana,grape"
6. SPLITA s BY "," TO a
7.  
8. t::sort(a)
9.  
10. FOR x = 0 TO UBOUND(a)
11.   PRINT a[x],"\n"
12. NEXT
13.  

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

1. ' Script BASIC Array Sort
2.  
3. IMPORT t.bas
4.  
5. OPEN "bible.txt" FOR INPUT AS #1
6. s = INPUT(LOF(1),1)
7. SPLITA s BY "\n" TO a
8.  
9. t::sort(a)
10.  
11. FOR x = UBOUND(a) - 10 TO UBOUND(a)
12.   PRINT a[x],"\n"
13. NEXT
14.  

Output

Code: [Select]

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.

Code: Script BASIC

1. ' Script BASIC Array Sort
2.  
3. IMPORT t.bas
4.  
5. s = "pear,apple,cranberry,orange,carrot,banana,grape"
6. SPLITA s BY "," TO a{"food"}
7.  
8. t::sort(a{"food"})
9.  
10. FOR x = 0 TO UBOUND(a{"food"})
11.   PRINT a{"food"}[x],"\n"
12. NEXT  
13.  

jrs@laptop:~/sb/sb22/test$ scriba arraysort.sb
apple
banana
carrot
cranberry
grape
orange
pear
jrs@laptop:~/sb/sb22/test$