Seven Bubble sort for you: which do you choose?

[Kernelpanic]

Without actual data to work with, it's impossible to say which sorting method is going to be the best or the fastest.

As far as I know, there is no the(!) fastest method. It depends on what one want to sort, what kind of data it is, and how much it is. - Difficult!

[SMcNeill]

Code: (Select All)

_Title "Only 1 pass to sort this out!"
d$ = "1,3,5,2,4,8,9,7,0,6,2,4,8,9,7,0,6,1,3,5,2,8,9,7,0,6,2"
Dim tracker(9) As Integer

p = InStr(d$, ",")
start = 1
While p
    index = Val(Mid$(d$, start, p - start))
    tracker(index) = tracker(index) + 1
    start = p + 1
    p = InStr(start, d$, ",")
Wend
index = Val(Mid$(d$, start)) ' last index

Print "sorted:"
For i = 0 To 9
    If tracker(i) Then
        For j = 1 To tracker(i)
            Print i;
        Next
    End If
Next

Aye.  As I've mentioned before, counting can often be the fastest means of sorting.  Only issue that comes up is if you spend more time counting than you would sorting.  For example, you DIMMED your data type as INTEGER -- *WHY* is the data here limited to 0 to 9?  

You have what here??  Almost 30 values in the data set?  If those values were from -32000 to +32000, then you'd have to change that FOR i loop to run 64000 times instead of 10.  Any decent sorting method should be able to run in fewer iterations than that.

There's no *always best* solution for sorting.  You really have to look at your needs, before deciding what  to go with, if ultimate performance is your goal.  

[DANILIN]

Russian Sorting Halves Danilin
2014 ... 2018 ... 2023
https://qb64forum.alephc.xyz/index.php?topic=702

I propose to introduce themes inside main program

Now program zapoln.bas synthesizes file ISX.txt
in program catalog

zapoln.bas

Code: (Select All)

n = 10^5: DIM d(n) ' zapoln.bas

a=1000
b=5000
c=3000
d=7000

RANDOMIZE TIMER

FOR i=1 TO INT(n/4)
    d(i)=INT(RND*100*a)+a
    d(n/4+i)=INT(RND*100*b)+b
    d(n/2+i)=INT(RND*100*c)+c
    d(3*n/4+i)=INT(RND*100*d)+d
NEXT

OPEN "ISX.txt" FOR OUTPUT AS #1

FOR i=1 TO n
PRINT #1, d(i): NEXT

END

Next, program rusort14.bas is sorting
first reads and then sorts 32767 integers
counting time and then writes to file rusort14.txt

rusort14.bas

Code: (Select All)

' DA 2 SIDE MASSIV sort rusort22.bas
n=32767

Dim d(2,n),q(3)

Open "ISX.txt" For Input As #1
For i=1 To n: Input #1,d(1,i): Next

For k=n-10 To n: Print d(1,k);: Next: Print
start=Timer: p=0: s=0

Print "SORTING": Print: Print

For i=1 To n: sum1=sum1+d(1,i): Next
sred1=sum1/n: Print sred1: Print

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
    '    FOR k=1 TO n: PRINT d(2,k);: NEXT: PRINT
Next: Print

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

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): p=p+1
        s=s+1: Next: '    FOR k=1 TO n: PRINT d(2,k);: NEXT: PRINT
    Next
Next

finish=Timer

For i=1 To n: sum3=sum3+d(2,i): Next: sred3=sum3/n: Print

For i=n-10 To n: Print d(2,i);: Next: Print
Print finish-start,s,p

Open "rusort14.txt" For Output As #2
For i=1 To n: Print #2,d(2,i): Next

Then it is possible to compare time
taking into account: my current version is with key 2
and there are developments for key 4 and key 8

Personally, if I translate into theme style
I think it will take too much time






All know ?

Quick sorting was invented in 1960
when author american was an in USSR

[TempodiBasic]

@DANILIN

Lol with the second video from youtube You have taeched me the algorythm  slower than Bubbllesort! 

[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

[TempodiBasic]

yes I heard somewhere from someone with a good knowledge of programming (sorry for the lackness of specific name and data)
sorting is always a dubt to solve, just changing a bit the scrambled set of items and you get very different results in performance of different algorithms for sorting.

Well let me just three months and I build some other sorting algorithms and after that we let run sequentially each one to get its performances using different data of a scrambled set to be ordered.
 fine to do.

[DANILIN]

Will you create new bubble sorting algorithms?

Topic specifically: bubble sorting algorithms

Please test my program
and post a picture of results independently of me
where Russian sorting halves is 2 times faster

111 kB

[TempodiBasic]

@DANILIN

Lol with the second video from youtube You have taeched me the algorythm  slower than Bubbllesort

Here I said that from the video of youtube that you have linked I learnt that Odd-Even sort is (or seems to be?) slower than Bubblesort, that is known for its slowness... and this is fun for me.


---

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

just for understanding your communication...
 1.  sorting halves is one kind of bubble algorithm?  
  (it does not appear to me looking at you code.)

2. Is russian sorting halves a russian version of an algorithm called "sorting halves", ie like Quicksort has different versions?

Thanks for feedback.

about 

Will you create new bubble sorting algorithms?

No, I have posted only those variations of Bubblesort that I have in my knowledge...
If you have another variation, I will glad to see it in this thread, if you want to share it.

Please test my program
and post a picture of results independently of me
where Russian sorting halves is 2 times faster

OK, I'll do. Please assure me that is a variation of Bubblesort algorithm

[DANILIN]

Yes Russian sorting halves is accelerated bubble sorting

Code: (Select All)

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)
Next: Next: Next

There is a recursive version approaching quick sort

Quick sort invente by an American in USSR in 1960

[TempodiBasic]

Yes Russian sorting halves is accelerated bubble sorting

Code: (Select All)

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)
Next: Next: Next

There is a recursive version approaching quick sort

Quick sort invente by an American in USSR in 1960

it seems to me that Russian sorting halves is a bublle sort variation only for this part of code that you have noted here above, but the rest part of your copyrighted algorithm is not bublle sort type!
You split into 2 sets of values under and above an aritmetic average the original unordered set of values and the you apply bubble sort to each subset.

So it is half bubble sort algorithm.