Author Topic: Array Sort  (Read 11762 times)

Support

  • Administrator
  • *****
  • Posts: 1
    • View Profile
Array Sort
« on: March 30, 2015, 04:59:07 am »
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
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
' 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)

' 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
 
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.

' 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$

« Last Edit: March 31, 2015, 07:04:04 am by support »