|
|
Post by johnno56 on May 13, 2020 21:00:12 GMT -6
Hi N00b,
Jumped onto rosettacode.org and managed to find a couple of sort routines. Bubble and Insertion. Of the two, Insertion, was almost 10 times faster than Bubble. Sorted 10,000 random numbers from 1 to 1000. Bubble: 166.69 secs and Insertion: 17.115 secs.
But I'm not sure how the function would be called....
Insertion Sort:
xmax = 400
ymax = 640
title$ = "Insertion Sort - I hope..."
WindowOpen(1,title$,windowpos_centered,windowpos_centered,xmax,ymax,0)
CanvasOpen(1,xmax,ymax,0,0,xmax,ymax,0)
setColor(rgb(255,255,255))
start = 0
finish = 0
maxSize = 10000
Dim a[maxSize + 1]
prints("Original set - 10000 random numbers - Generating")
for i = 0 to maxSize - 1
a[i] = rand(1000) + 1
'prints(str(a[i]))
next
i = 0
j = 0
t = 0
prints("Start: " + str(start))
start = timer()
for i = 1 to maxSize - 1
t = a[i]
j = i
while j > 0 and t < a[abs(j - 1)]
a[j] = a[j - 1]
j = j - 1
wend
a[j] = t
next
prints("... sorted")
finish = timer() - start
prints("Finish: " + str(finish / 1000))
waitkey
Bubble Sort
xmax = 400
ymax = 640
title$ = "Bubble Sort - I hope..."
WindowOpen(1,title$,windowpos_centered,windowpos_centered,xmax,ymax,0)
CanvasOpen(1,xmax,ymax,0,0,xmax,ymax,0)
setColor(rgb(255,255,255))
start = 0
finish = 0
maxSize = 10000
Dim a[maxSize + 1]
ordered = false
prints("Original set - 10000 random numbers - Generating")
For n = 0 to maxSize - 1
a[n] = rand(1000) + 1
'prints(str(a[n]))
next
' algorithm
prints("... sorting")
prints("Start: " + str(start / 1000))
start = timer()
update()
while ordered = false
ordered = true
For n = 0 to maxSize - 1
if a[n] > a[n + 1] then
x = a[n]
a[n] = a[n + 1]
a[n + 1] = x
ordered = false
end if
next
update()
wend
finish = timer() - start
prints("Finish: " + str(finish / 1000))
prints("Sorted")
update()
waitkey
There are a whole lot more sort algorithms....
|
|
|
|
Post by n00b on May 14, 2020 1:11:14 GMT -6
You can use ByRef to write directly to an array passed to the function. I will try to post an example soon. Its pretty late here so I am going to go count sheep.
|
|
|
|
Post by Tomaaz on May 14, 2020 10:18:38 GMT -6
166 sec? I know bubble sort is slow, but I just tried it on my old laptop. Ruby - 25 sec. Crystal (compiled Ruby-like language) - 5 sec.
tablica = []
10000.times do
tablica << rand(1001)
end
unsorted = true
z = 1
while unsorted
(z..tablica.size - 1).each do |x|
if tablica[x - 1] > tablica[x]
tablica[x], tablica[x - 1] = tablica[x - 1], tablica[x]
if x == tablica.size - 1
unsorted = false
end
if z > 1
z = x - 2
else
z = 1
end
break
else
z = x
end
end
end
x = tablica.size - 2
while tablica[x] < tablica[x - 1]
tablica[x], tablica[x - 1] = tablica[x - 1], tablica[x]
x -= 1
end
print tablica
Of course, built-in method for sorting is much faster...
|
|
|
|
Post by Tomaaz on May 14, 2020 10:32:16 GMT -6
My point is that this kind of stuff should be done in compiled languages.
|
|
|
|
Post by n00b on May 14, 2020 15:27:08 GMT -6
johnno56I took your sorting code and made a SUB with BYREF argument for the array. You can use this as an example. Sub Insertion_Sort(Byref a, a_size)
i = 0
j = 0
t = 0
start = timer()
for i = 1 to a_size - 1
t = a[i]
j = i
while j > 0 and t < a[abs(j - 1)]
a[j] = a[j - 1]
j = j - 1
wend
a[j] = t
next
End Sub
xmax = 400
ymax = 640
title$ = "Insertion Sort - I hope..."
WindowOpen(1,title$,windowpos_centered,windowpos_centered,xmax,ymax,0)
CanvasOpen(1,xmax,ymax,0,0,xmax,ymax,0)
setColor(rgb(255,255,255))
start = 0
finish = 0
maxSize = 10000
Dim a[maxSize + 1]
prints("Start: " + str(start))
prints("Original set - 10000 random numbers - Generating")
for i = 0 to maxSize - 1
a[i] = rand(1000) + 1
'prints(str(a[i]))
next
Insertion_Sort(a, maxSize)
prints("... sorted")
finish = timer() - start
prints("Finish: " + str(finish / 1000))
waitkey
My point is that this kind of stuff should be done in compiled languages. Yes a compiled language will be faster. However, for the sorting routines johnno56 made, especially the insertion sort, I think these are more than fast enough for use in most cases that RCBasic would be used for. If you are trying to sort 10,000 elements at runtime you are probably doing something wrong. 
|
|
|
|
Post by johnno56 on May 14, 2020 16:52:16 GMT -6
Many thanks for the "sub" much appreciated. I too think that the Insertion sort will be fast enough for RC's needs... I only tried Bubble, quick and Insertion from the list of many. I haven't tested the speed of the other routines. Perhaps one of those would be more suited for larger collection of elements...
I initially chose 1,000 elements but it sorted too quickly... lol Minuscule sort time... So I put it up to 10,000. I did try 100,000 but the poor sort routine (bubble) was working its innards out (2+ minutes!) so I terminated it and kept it at 10,000 and switched to Insertion.
|
|
|
|
Post by tbird on May 14, 2020 19:20:33 GMT -6
Going to have to keep updating the first post as we add stuff to this helpful topic.
|
|
|
|
Post by Tomaaz on May 16, 2020 12:16:15 GMT -6
I always thought that bubble sort algorithm was the easiest one, but insertion sort is even easier, so I decided to check in in Crystal.
class Array
def insort
tablica = self
(1..tablica.size - 1).each do |y|
x = y
z = tablica[y]
while tablica[y] < tablica[x - 1] && x > 0
x -= 1
end
tablica.delete_at(y)
tablica.insert(x, z)
end
result = tablica
end
end
liczby = [] of Int32
10000.times {liczby << rand(1001)}
liczby.insort
For 10000 elements it's OK (1 sec.), but it takes several minutes to sort random 100000 elements, while built-in sort method takes a couple of seconds to sort one million of random elements. You're probably right that it will be enough for RCBasic, but generally it's not the best option.
|
|
