Seven Bubble sort for you: which do you choose?

[TempodiBasic]

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

[DANILIN]

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

[TempodiBasic]

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.

[TempodiBasic]

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

[TempodiBasic]

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

[DANILIN]

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...1#pid14341

for 500 elements
and show pictures with seconds

I think result of old program will be better

[TempodiBasic]

@DANILIN

hey boy put on your glasses,  you read 500 instead of 5000! Lol keep calm and code QB64!

[DANILIN]

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...1#pid14341

my results: it used to be faster

[TempodiBasic]

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...1#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.

[david_uwi]

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