RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-19-2023
Hi
here a recursive vs iterative methods demonstration about bubblesort the original algorithm:
Code: (Select All) $Debug
Const max = 5 '32767
Randomize Timer
Type DATATYPE
a As Integer
b As Integer
c As Integer
End Type
ReDim SortedList(1 To max) As DATATYPE, t(1 To max) As DATATYPE
'The sort will only be done on the value of 'a' (SortedList().a) and the values can range from 1 to 32767.
init SortedList() ' this is the original array created at random
initT SortedList(), t() ' this copies the first array into the second array
Print "original array "
ShowArray t()
_Delay 2
BubbleRecursive t(), 0, 0
Color 3
Print " Bubble Recursive order"
ShowArray t()
Color 7
Print "press a key to continue...";
Sleep
initT SortedList(), t()
Print "Original array"
ShowArray t()
_Delay 2
Print "ordering..."
bubble t()
Color 2
Print "Bubble Iterative order"
ShowArray t()
Color 7
_Delay 2
End
Sub BubbleRecursive (a() As DATATYPE, Noswap As Integer, c As Integer)
If Noswap = 0 Then
Noswap = -1
If c < (max - 1) Then
c = c + 1
If a(c).a > a(c + 1).a Then
Swap a(c).a, a(c + 1).a
Noswap = 0
End If
Else
' c => max-1
If Noswap = 0 Then c = 1
End If
BubbleRecursive a(), Noswap, c
End If
End Sub
Sub bubble (a() As DATATYPE)
' bubblesort
' we compare 2 sequential elements of a set of elements until no swap has been performed
' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
NoSwap = 0
While NoSwap = 0
NoSwap = -1
For count = 1 To max - 1
If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
Next count
Wend
End Sub
Sub initT (b() As DATATYPE, a() As DATATYPE)
For count = 1 To max
a(count).a = b(count).a
Next count
End Sub
Sub init (a() As DATATYPE)
For count = 1 To max
a(count).a = (Rnd * max - 1) + 1
Next count
End Sub
Sub ShowArray (A() As DATATYPE)
For count = 1 To max
Print A(count).a
Next count
End Sub
RE: Seven Bubble sort for you: which do you choose? - DANILIN - 03-20-2023
You accidentally forgot to post a picture of results
Start newest program several times
and there will be cases when it sorts incorrectly
I have your newest program sorting time does not write
RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-21-2023
(03-20-2023, 03:43 AM)DANILIN Wrote: You accidentally forgot to post a picture of results
Start newest program several times
and there will be cases when it sorts incorrectly
I have your newest program sorting time does not write
Hi DANILIN
thanks for feedbacks:
Gosh I thought I fix the recursive method... but it need more fixing!
Sorry for bad code.
I need rest and then I'll be able to fix it.
RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-22-2023
Hi
here a working version of RecursiveBubble sort algorithm, it uses a recursion with two subprograms (2 SUBs).
take a run!
Code: (Select All) _Title "Bubble recursive method vs Bubble classic mode"
Const max = 5 '32767
Randomize Timer
Type DATATYPE
a As Integer
b As Integer
c As Integer
End Type
ReDim SortedList(1 To max) As DATATYPE, t(1 To max) As DATATYPE
'The sort will only be done on the value of 'a' (SortedList().a) and the values can range from 1 to 32767.
init SortedList() ' this is the original array created at random
initT SortedList(), t() ' this copies the first array into the second array
Print "original array "
ShowArray t()
_Delay 2
BubbleRecursive t(), 0, 0
Color 3
Print " Bubble Recursive order"
ShowArray t()
Color 7
Print "press a key to continue...";
Sleep
initT SortedList(), t()
Print "Original array"
ShowArray t()
_Delay 2
Print "ordering..."
bubble t()
Color 2
Print "Bubble Iterative order"
ShowArray t()
Color 7
_Delay 2
End
Sub BubbleRecursive (a() As DATATYPE, Noswap As Integer, c As Integer)
If Noswap = 0 Then
Noswap = -1
BubbleRecursiveB a(), Noswap, 0
If Noswap = 0 Then BubbleRecursive a(), Noswap, c
End If
End Sub
Sub BubbleRecursiveB (a() As DATATYPE, NoSwap As Integer, c As Integer)
If c < (max - 1) Then
c = c + 1
If a(c).a > a(c + 1).a Then
Swap a(c).a, a(c + 1).a
NoSwap = 0
End If
BubbleRecursiveB a(), NoSwap, c
Else
' c => max-1c
End If
End Sub
Sub bubble (a() As DATATYPE)
' bubblesort
' we compare 2 sequential elements of a set of elements until no swap has been performed
' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
NoSwap = 0
While NoSwap = 0
NoSwap = -1
For count = 1 To max - 1
If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
Next count
Wend
End Sub
Sub initT (b() As DATATYPE, a() As DATATYPE)
For count = 1 To max
a(count).a = b(count).a
Next count
End Sub
Sub init (a() As DATATYPE)
For count = 1 To max
a(count).a = (Rnd * max - 1) + 1
Next count
End Sub
Sub ShowArray (A() As DATATYPE)
For count = 1 To max
Print A(count).a
Next count
End Sub
and these are two different instances of it
RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-22-2023
Hey
I have forgotten the DANILIN perspective...
code + screenshot of results....
here I can respect DANILIN perspective
Code: (Select All) _Title "Bubble recursive method vs Bubble classic mode"
Const max = 5000 '32767
Randomize Timer
Type DATATYPE
a As Integer
b As Integer
c As Integer
End Type
Dim As Double T1, T2
ReDim SortedList(1 To max) As DATATYPE, t(1 To max) As DATATYPE
'The sort will only be done on the value of 'a' (SortedList().a) and the values can range from 1 to 32767.
init SortedList() ' this is the original array created at random
initT SortedList(), t() ' this copies the first array into the second array
Print "original array "
ShowArray t()
_Delay 2
T1 = Timer(0.001)
BubbleRecursive t(), 0, 0
T1 = Timer(0.001) - T1
Color 3
Print " Bubble Recursive order"
ShowArray t()
Color 7
Print "press a key to continue...";
Sleep
initT SortedList(), t()
Print "Original array"
ShowArray t()
_Delay 2
Print "ordering..."
T2 = Timer(0.001)
bubble t()
T2 = Timer(0.001) - T2
Color 2
Print "Bubble Iterative order"
ShowArray t()
Color 7
_Delay 2
Print " Recursive Bubble Sort: time used "; T1
Print " Iterative Bubble Sort: time used "; T2
End
Sub BubbleRecursive (a() As DATATYPE, Noswap As Integer, c As Integer)
If Noswap = 0 Then
Noswap = -1
BubbleRecursiveB a(), Noswap, 0
If Noswap = 0 Then BubbleRecursive a(), Noswap, c
End If
End Sub
Sub BubbleRecursiveB (a() As DATATYPE, NoSwap As Integer, c As Integer)
If c < (max - 1) Then
c = c + 1
If a(c).a > a(c + 1).a Then
Swap a(c).a, a(c + 1).a
NoSwap = 0
End If
BubbleRecursiveB a(), NoSwap, c
Else
' c => max-1c
End If
End Sub
Sub bubble (a() As DATATYPE)
' bubblesort
' we compare 2 sequential elements of a set of elements until no swap has been performed
' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
NoSwap = 0
While NoSwap = 0
NoSwap = -1
For count = 1 To max - 1
If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
Next count
Wend
End Sub
Sub initT (b() As DATATYPE, a() As DATATYPE)
For count = 1 To max
a(count).a = b(count).a
Next count
End Sub
Sub init (a() As DATATYPE)
For count = 1 To max
a(count).a = (Rnd * max - 1) + 1
Next count
End Sub
Sub ShowArray (A() As DATATYPE)
For count = 1 To max
Print A(count).a
Next count
End Sub
with results output
RE: Seven Bubble sort for you: which do you choose? - DANILIN - 03-23-2023
it would seem obvious: it is important to check
all programs by 32767 elements
and show pictures with seconds
however newest program on 32767 turns off
then it is important to check old program from message 15
https://qb64phoenix.com/forum/showthread.php?tid=1540&pid=14341#pid14341
for 500 elements
and show pictures with seconds
I think result of old program will be better
RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-23-2023
@DANILIN
hey boy put on your glasses, you read 500 instead of 5000! Lol keep calm and code QB64!
RE: Seven Bubble sort for you: which do you choose? - DANILIN - 03-23-2023
my computer is slower than yours
so it's better if you check
elements 500 or 5000 or 32767
it is important to check in new sorting
and be sure in full version
https://qb64phoenix.com/forum/showthread.php?tid=1540&pid=14341#pid14341
my results: it used to be faster
RE: Seven Bubble sort for you: which do you choose? - TempodiBasic - 03-23-2023
(03-23-2023, 05:06 AM)DANILIN Wrote: my computer is slower than yours
so it's better if you check
elements 500 or 5000 or 32767
it is important to check in new sorting
and be sure in full version
https://qb64phoenix.com/forum/showthread.php?tid=1540&pid=14341#pid14341
my results: it used to be faster
Hi DANILIN
setting max = 32767 the recursive program crashes, so it is impossible for me measuring its performance. The recursive program need more and more RAM than that on my PC.
BUT I must say that the recursive version has been coded as exercise and not to be faster than the iterative version.
So I must agree that your mixbubble version is the fastest showed into this thread.
RE: Seven Bubble sort for you: which do you choose? - david_uwi - 03-24-2023
For small data sets (<5000) I always use select sort.
It is easy to code.
It always works.
It always takes the same amount of time.
For larger data set some there are much better routines, but I don't understand how they work - some kind of splitting and pivoting -magic in other words.
Code: (Select All) DefInt A-S
kdim = 32767
Dim x(kdim)
For i = 1 To kdim
x(i) = Rnd * 1000
Print x(i),
Next i
Print
tt = Timer
For j = 1 To kdim \ 2
jmax = j: xmax = x(j)
jmin = kdim - j + 1: xmin = x(kdim - j + 1)
For i = j + 1 To kdim - j + 1
If x(i) > xmax Then jmax = i: xmax = x(i)
If x(i) < xmin Then jmin = i: xmin = x(i)
Next i
Swap x(j), x(jmax)
Swap x(kdim - j + 1), x(jmin)
Next j
Print Timer - tt
Input sa$
For i = 1 To kdim
Print x(i),
Next i
Print
|