Seven Bubble sort for you: which do you choose?

[TempodiBasic]

Hi QB64 Community

I have heard in the air a spealing that said "Bubble sort!"
It let me remember a old fashioned book of programming in Pascal. An just then this the "bubble gum".
So while I go to Psychoanalyst to set up better my mind here a Demonstration of different ways to build up a Bubble Sort routine...
in sum their are seven different routines... the first is the classical version, then it follows the last_index decreasing, the last_index swaped, the split & compact with different dimensions for splitting and one of the two index optimized manners...
run and choose you preferred BUBBLE SORT algorithm...
here I show the result got running the following code




and here the code:

Code: (Select All)

Const max = 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 "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble t()
Print t(1).a, t(max - 1).a, t(max).a
Color 1
Print " Bubble 1 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t() ' so we use the identical array to be ordered
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble2 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 2
Print " Bubble 2 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble3 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 3
Print " Bubble 3 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble4 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 4
Print " Bubble 4 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble5 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 5
Print " Bubble 5 order"
Print (Timer(.001) - t#)
Color 7

initT SortedList(), t()
Print "output the first and the last 2 items ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble6 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 6
Print " Bubble 6 order"
Print (Timer(.001) - t#)
Color 7


End

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 bubble2 (a() As DATATYPE)
    ' bubblesort
    ' we compare 2 sequential elements of a set of elements until no swap has been performed
    ' but we ignore the last elements because they has been already ordered
    ' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
    NoSwap = 0
    Fmax = max
    While NoSwap = 0
        NoSwap = -1
        Fmax = Fmax - 1
        For count = 1 To Fmax
            If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
        Next count
    Wend
End Sub

Sub bubble3 (a() As DATATYPE)
    ' bubblesort
    ' we compare 2 sequential elements of a set of elements until no swap has been performed
    ' but we ignore the last elements because they has been already ordered by swap
    ' while the first element is higher/lower (increasing/decreasing order) than the second element we swap the 2 elements
    NoSwap = 0
    Last = max - 1
    While NoSwap = 0
        NoSwap = -1
        For count = 1 To Last
            If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0: Last = count
        Next count
    Wend
End Sub

Sub bubble4 (a() As DATATYPE)
    ' this is multibubble
    ' we split the array if too big into many subarray ordered by bubble sort
    ' using as max bubble dimension to order 3200 item for array
    stepB = UBound(a) / 3200
    For index = 1 To (UBound(a) - stepB) Step stepB

        ' bubble2 type
        NoSwap = 0
        First = index
        Last = index + stepB - 1
        While NoSwap = 0
            NoSwap = -1
            Last = Last - 1
            For count = First To Last
                If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0
            Next count
        Wend

    Next
    bubble2 a() ' the last ordering operation
End Sub



Sub bubble5 (a() As DATATYPE)
    ' this is multibubble
    ' we split the array if too big into many subarray ordered by bubble sort
    ' using as max bubble dimension to order 100 item for array
    stepB = UBound(a) / 100
    For index = 1 To (UBound(a) - stepB) Step stepB

        ' bubble3 type
        NoSwap = 0
        First = index
        Last = index + stepB - 1
        While NoSwap = 0
            NoSwap = -1
            For count = First To Last
                If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0: Last = count
            Next count
        Wend

    Next
    bubble3 a() ' the last ordering operation
End Sub





Sub bubble6 (a() As DATATYPE)
    ' this is multibubble
    ' we split the array if too big into many subarray ordered by bubble sort
    ' using as max bubble dimension to order 1000 item for array
    stepB = UBound(a) / 1000
    For index = 1 To (UBound(a) - stepB) Step stepB

        ' bubble3 type
        NoSwap = 0
        First = index
        Last = index + stepB - 1
        While NoSwap = 0
            NoSwap = -1
            For count = First To Last
                If a(count).a > a(count + 1).a Then Swap a(count), a(count + 1): NoSwap = 0: Last = count
            Next count
        Wend

    Next
    bubble3 a() ' the last ordering operation
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

Thanks to make your choice!