ErosOlmi
18-03-2007, 11:16
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
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
18-03-2007, 22:56
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
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
18-03-2007, 23:05
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
21-02-2024, 05:13
Have you considered using a wiki for maintaining and sharing these code samples for the thinBasic community, as suggested by kryton9?
ErosOlmi
21-02-2024, 21:36
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 :D
paravantis
24-08-2024, 15:41
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
25-08-2024, 00:24
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
25-08-2024, 13:00
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"
ErosOlmi
26-08-2024, 12:27
Ciao John
I've created a little script for testing and here it seems sorting just fine.
I think there must be something else somewhere that corrupt the array data type or the array size or how data is loaded into array
Here below my script that seems working fine here
If you still have the problem, can you please create a short script showing the problem?
Thanks a lot
Eros
#MinVersion 1.13
uses "console"
dim Numbers(100) as double =
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
WaitKey(0, "Press a key to proceed: showing array data before and after sorting")
printl "Numbers before sorting:"
PrintArray(Numbers)
WaitKey(0, "Press a key to sort array")
array sort Numbers
PrintArray(Numbers)
WaitKey(0, "Press a key to sort end")
function PrintArray(byref lArray() as double)
long n
for n = 1 to ubound(lArray)
print format$(n, "000") in %CCOLOR_LIGHTBLUE, format$(lArray(n), "+#0.000000000;-#0.000000000; #0.000000000"), " "
if mod(n, 5) = 0 then printl
Next
End Function
paravantis
26-08-2024, 17:06
Your script helped me pinpoint the issue.
I was using Array Sort to sort all the elements (including empty cells) of an array that was DIMed to a value higher than the number of data points entered into it.
As a result, Array Sort was correctly bringing in all the zero values of the empty cells right after the negative data points.
In my program, I now use
Array Sort xSort(1) for x4Sort
where x4Sort is the actual number of values entered into the array.
Problem solved, grazie tante Eros!
ErosOlmi
26-08-2024, 17:42
Your post also helped me.
Next thinBasic version 1.13.1 (out in few weeks) will have automatic dimensioning of string and numeric arrays when data is passed during variable declaration.
I've also some other ideas I will work on.
Will study how other languages syntax about this (php, javascript, python, ...) in order to simplify programmer's life.
10385