Seven Bubble sort for you: which do you choose?

[DANILIN]

Good laughs who laughs at everyone

Experience 8 sorts

Only Sorting No.1 is simplest
for some reason it writes 0 and I replaced to end

But "Russian sorting halves (c)" works 2 times faster
and I remind you: it is possible to work 8 times faster
than bubble sorting

Plus I have a state certificate of authorship

I trust readers to create pictures: you have faster PC

Code: (Select All)

Const max = 32767 ' RSHsorting.bas
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 "Russian Sorting Halves Danilin        ";
Print t(1).a; " "; t(max - 1).a; " "; t(max).a
t# = Timer(.001)
Print "ordering...";
bubble8 t()
Print t(1).a, t(max - 1).a, t(max).a
Color 4
Print " Bubble Russian order";
Print (Timer(.001) - t#): Print
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

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

End

Sub bubble8 (a() As DATATYPE)
    ' Russian Sorting Halves Danilin

    Dim d(2, max), q(3): n = max
    For i = 1 To max: d(1, i) = a(i).a: Next
   
    For i = 1 To max: sum1 = sum1 + d(1, i): Next: sred1 = sum1 / n

    y = 1: z = 0: For i = 1 To n
        If d(1,i) < sred1 Then d(2,y) = d(1,i): y=y+1: Else d(2,n-z) = d(1,i): z=z+1
    Next:

    For i = 1 To n: sum2 = sum2 + d(2, i): Next: sred2 = sum2 / n

    q(1) = 1: q(2) = y - 1: q(3) = n

    For t = 1 To 2
        For i = q(t) To q(t + 1): For j = i + 1 To q(t + 1)
            If d(2, i) > d(2, j) Then Swap d(2, i), d(2, j)
            s = s + 1: Next
        Next
    Next
    For count = 1 To max
        a(count).a = d(2, count)
    Next count

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 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