Sorting arrays with built-in sorting functions

[ErosOlmi]

Sorting numeric arrays?
Using built-in sorting functions it can take ... no time.

 '---Globals
 DIM MaxCount     AS LONG value 100000
 dim MyArray(MaxCount) as long
 dim Count      as long
 dim T1, T2      as double
 DIM Message     AS STRING

 '---Ask if execute or not
 Message = "This program will fill an array of " & MaxCount & " elements with random LONG numbers.\n"
 Message += "Array will be sorted twice in order to test sorting of sparse and already sorted array.\n\n"
 Message += "Please press Yes to go on, NO to Stop\n"
 DIM lResult AS LONG = MSGBOX(0, Message, %MB_YESNO, "Continue?")
 IF lResult <> %IDYES THEN
  STOP
 END IF

 '---Speed up operations a bit
 doevents(off)

 '---Init random number generator
 randomize
 
 '---Fill array with random numbers
 T1 = GetTickCount
 for Count = LBound(MyArray) To UBound(MyArray) 
  MyArray(Count) = rnd(-1000000000, 1000000000) 
 next 
 T2 = GetTickCount


 '---Do the job
 msgbox 0, _
     "Time to fill randomly an array of " & ubound(MyArray) & " elements:" & $tab & format$(T2-T1) & " mSecs" & $crlf & _
     "Time to sort array "               & repeat$(5, $tab) & testsort(MyArray)     & " mSecs" & $crlf & _
     "Time to re-sort sorted array "          & repeat$(4, $tab) & testsort(MyArray)     & " mSecs" & $crlf & _
     "Time to re-sort sorted array in descending order " & repeat$(2, $tab) & testsort(MyArray, %TRUE) & " mSecs" & $crlf & _
     ""

 '----------------------------------------------------------------------------
 '---In case you want to see some output values, just uncomment those lines
 '----------------------------------------------------------------------------
 'uses "console"
 'for count = 1 to 80
 ' console_write MyArray(Count) & ", "
 'next
 'console_waitkey 
 
 '----------------------------------------------------------------------------
 '---Sorting function
 '----------------------------------------------------------------------------
 Function TestSort(byref v() as long, optional DeScendSorting as long) as long
  
  '---Time measuring vars
  local ticka, tickb as double
  
  '---Start timer
  ticka = GetTickCount
  
  '---Sort array passed by reference depending on sort order
  if DeScendSorting = %TRUE then
   array sort v, descend
  else
   array sort v
  end if

  '---ENd timer
  tickb = GetTickCount
  function = tickb - ticka 
  
 End Function

[kryton9]

Awesome we need these kind of samples Eros, thanks so much. You might want to talk with Roberto, he had an interesting idea of placing all of these in a repository so easy to find.

[ErosOlmi]

Repository is already there at http://scripts.thinbasic.com/ but abandoned.
I did it almost one year ago but at that time it was not the right time.

I will consider your wiki suggestion checking which is the best around.
I want it easy to be used and with syntax highlight.

Ciao
Eros

[kryton9]

Bookmarked, never saw it or don't remember that. I would sticky that to the top or put in the menubar on the forums for sure. Great!!

[ErosOlmi]

Ken,

we are not maintaining it anymore.
I will delete it and substitute with a new one after choosing the best we can find.
So continue your suggestion about wiki. I will follow it and in the meantime try to find what will be better for thinBasic community.

Ciao
Eros

[Limaxdum]

Have you considered using a wiki for maintaining and sharing these code samples for the thinBasic community, as suggested by kryton9?

[ErosOlmi]

Have you considered using a wiki for maintaining and sharing these code samples for the thinBasic community, as suggested by kryton9?

Those messages posted by AI bot are doing great job

[paravantis]

Trying to sort (ascending) the following 100 numbers using ARRAY SORT

0.508210507
2.271638259
0.76078255
0.957525991
-2.387695394
0.795957904
0.693785993
-1.188321733
1.381440343
-0.461175478
1.489988646
0.750147094
0.527872561
-0.411497533
-0.634290479
0.178526739
1.285337463
-1.051731613
0.545955657
0.577297228
0.231946769
0.45728207
-0.735775852
-0.127960995
0.005307588
-0.050718714
0.524725502
0.295784074
-0.107940309
0.156720754
-0.941050506
-1.157671044
-0.323071971
0.148512737
-0.83228278
0.265810425
0.01064563
-0.028561661
1.846478155
0.217954152
1.364586147
-0.246613086
0.913975039
1.219781021
-1.100125379
-0.698041051
0.934720676
-0.982526268
0.502026823
-0.45267955
0.442353055
0.148805418
1.31759004
1.209563127
0.982567037
-0.760403384
0.070782254
1.374120987
-0.122692461
-0.174001986
0.807553832
0.160879446
0.979111885
0.407008646
0.750277918
-1.341988943
1.798166935
-0.014998984
-0.012918439
1.202851974
0.57190789
-0.730953737
1.19712005
1.086329786
-0.110994885
1.271766978
-1.695791348
1.127182143
-0.738788445
-0.362852264
1.029229745
-0.068066658
1.06387776
0.415527493
-0.225864695
-0.416020166
2.198364013
-0.809310952
-1.532119923
-0.542072656
-0.422387603
0.431662509
0.706261533
-0.823930064
0.011530519
-0.449438784
-0.286756
1.372709007
0.657282984
-0.147238732

gave me the following results for the sorted array

-2.387695394
-1.695791348
-1.532119923
-1.341988943
-1.188321733
-1.157671044
-1.100125379
-1.051731613
-.982526268
-.941050506
-.83228278
-.823930064
-.809310952
-.760403384
-.738788445
-.735775852
-.730953737
-.698041051
-.634290479
-.542072656
-.461175478
-.45267955
-.449438784
-.422387603
-.416020166
-.411497533
-.362852264
-.323071971
-.286756
-.246613086
-.225864695
-.174001986
-.147238732
-.127960995
-.122692461
-.110994885
-.107940309
-.068066658
-.050718714
-.028561661
-.014998984
-.012918439
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

In other words, the sorting algorithm seems to have worked up to a certain point but then placed zeroes after a specific value.

It appears that these zero values have actually replaced some of the positive data values!

Can you confirm?

With my best regards from the University of Piraeus in Greece,
John Paravantis

[paravantis]

By the way, I wrote a small program (as part of a larger statistical app I've been developing in my spare time) that implements Shell sort. It's incredibly fast:

'/////////////////////
'// Shell sort data //
'/////////////////////

' Array to sort: xSort(1..xN)

DIM sGap,sj,sk as Long

dim tSeconds as Double
print "  Shell sorting data ... ";
HiResTimer_Init

sGap=xN\2

Do
   for sj=sGap to xN
      for sk=sj-sGap to 1 step -sGap
         if xSort(sk+sGap)>=xSort(sk) Then
            exit For
         else
            swap xSort(sk+sGap),xSort(sk)
         end If
      Next
   Next
   sGap=sGap\2
loop while sGap>0

tSeconds=round(HiResTimer_Delta/10^6,3)
printl "done in "+tSeconds+" seconds"

[paravantis]

And here is a similar routine implementing comb sort, an improvement over bubble sort, also blinding fast and in some cases even faster than Shell sort:

'////////////////////
'// Comb sort data //
'////////////////////

' Array to sort: xSort(1..xN)

dim tSeconds as Double

print "  Comb sorting data ... ";

dim c_sm as Long
dim c_shrink as Double
dim c_gap as long
dim c_sorted as Boolean
dim c_i as Long

c_shrink=1.3 ' Optimal for comb short
c_gap=xN
c_sorted=FALSE

HiResTimer_Init

while (not c_sorted)

   c_gap=int(c_gap/c_shrink)

   if (c_gap<=1) Then
      c_sorted=TRUE
      c_gap=1
   end If

   for c_i=1 to xN-c_gap
      c_sm=c_gap+c_i
      if xSort(c_i)>xSort(c_sm) Then
          swap xSort(c_i),xSort(c_sm)
          c_sorted=FALSE
      end If
   Next

wend

tSeconds=round(HiResTimer_Delta/10^6,3)
printl "done in "+tSeconds+" seconds"