Author Topic: Array Sort  (Read 15011 times)

Support

  • Administrator
  • *****
  • Posts: 22
    • View Profile
Array Sort
« on: March 29, 2015, 09:59:07 PM »
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$

« Last Edit: March 31, 2015, 12:04:04 AM by support »