[RESOLVED] The Logic Behind Bubble Sort | How does it work?

[Snowy Mexican]

Hey everyone,

So I was recently introduced to bubble sorting in VB 6 but I'm still struggling to understand how it works. Would anyone be willing to provide me with an algorithm and explaining how it works? I've looked online but the explanations were rather complex and I'm wondering if there was a simpler way of explaining it.

Thanks,


Snowy

[PlausiblyDamp]

https://www.toptal.com/developers/sorting-algorithms has a nice animation of several sorting routines, doesn't explain the code as such but the visualisation gives you an idea of the logic behind the process.

[Snowy Mexican]

Hello Plaus,

I had a look at the animation for the bubble sort but I find it hard to understand without any values to sort. The animation is rather quick as well, however I appreciate the help.

Regards,

Snowy

[Arnoutdv]

This is the basic:
https://www.youtube.com/watch?v=P00xJgWzz2c

[techgnome]

simplistic explanation - bubble sort sorts values by "bubbling" higher values towards the end (or lower values to the beginning). It does this by comparing one value to the next value in the set... if the first value is larger than the next, it swaps them. It then compares the value again to the next value, swapping as needed. This process is repeated on down until either you run out of values to compare the initial value to - meaning it is the largest value of the set and it has now "bubbled" to the end where it belongs; or, the next value is larger... in which case it is in the right spot. Then the process resets and goes back to the beginning to start the process all over again.
It is one of the most basic, easiest sorts there is... it also happens to be one of the most inefficient.

-tg

[rdee]

BubbleSort makes sense if you are adding items to an already sorted list. In this particular circumstance bubblesort is arguably the most efficient algorithm to use.

Rdee

[Elroy]

BubbleSort makes sense if you are adding items to an already sorted list. In this particular circumstance bubblesort is arguably the most efficient algorithm to use.

Oh gosh, I guess I'll jump in.

Rdee, I hate to say it, but that's just not true. It somewhat depends on whether the items being added are going into random spots in the list, or possibly going in more frequently at certain spots, such as near the beginning or near the end.

However, in either case, a bubble-sort is probably not the answer. If you're adding random items, a left-right-up three pointer system defining a binary-tree is lightening fast (much faster than a bubble-sort). Also, to take it to yet another level of complexity, hash-tables have been shown to be even faster, and possibly better at handling more variety when it comes to where the new items are likely to be added. Personally, I really like B-trees, possibly because of their simplistic elegance.

Take Care,
Elroy

EDIT1: Just as an FYI, the VB6 Collection object uses the three-pointer binary-tree approach.

[techgnome]

I thought about getting into other sorts, but given the way the first post was worked it sounded like a student who's having trouble grasping the concepts behind the algo of a bubble sort, and this was part of an assignment...

-tg

[Elroy]

Well, "sorting" and "keeping something sorted" are really two separate topics. If we confine ourselves to how to best sort an unsorted list that's been handed to us, that in itself can be an involved topic. I suppose, just initially, we have the issues of simplicity (which a bubble-sort has), speed (which a bubble-sort doesn't have), and also such things as whether it's memory-based or disk-based. If it's disk-based, you get into such things as reading portions of the list into memory, sorting, and then writing back out. In these cases, disk I/O can be a factor in the sort's speed. As can be seen, it's not a straight-forward topic.

[I Love VB6]

Maybe this will help

[Elroy]

Here, I polished a bit on an old QuickSort routine I've had lying around for decades.

Just throw a Command1 and List1 onto a new project's Form1, and then add this code to the Form1:

Option Explicit
'

Private Sub Command1_Click()
    Dim s() As String
    Dim i As Long
    Const iLbound = -5
    Const iUbound = 5
    '
    ReDim s(iLbound To iUbound)
    '
    For i = iLbound To iUbound
        s(i) = sRandomString(8)
    Next i
    For i = iLbound To iUbound
        QuickSortStrings s
    Next i
    List1.Clear
    For i = iLbound To iUbound
        List1.AddItem s(i)
    Next i
End Sub

Public Sub QuickSortStrings(s() As String)
    ' Lbound and Ubound can be anything.
    ' No check for whether s() is dimensioned.
    '
    Dim iJumps() As Long
    Dim sCmp As String
    Dim sSwp As String
    Dim iMkr As Long
    Dim iLp1 As Long
    Dim iLp2 As Long
    Dim iTmp As Long
    Dim iJmp As Long
    Dim iCnt As Long
    Dim iLbd As Long
    '
    iCnt = UBound(s) - LBound(s) + 1&
    iLbd = LBound(s)
    If iCnt < 2& Then Exit Sub
    ReDim iJumps(0& To 99&)
    '
    iJumps(0&) = 1&
    iJumps(1&) = 4&
    iJumps(2&) = 13&
    iMkr = 0&
    Do While iJumps(iMkr + 2&) < iCnt
        iMkr = iMkr + 1&
        If iMkr + 2& > UBound(iJumps) Then ReDim Preserve iJumps(LBound(iJumps) To UBound(iJumps) + 100&)
        iJumps(iMkr + 2&) = 3& * iJumps(iMkr + 1&) + 1&
    Loop
    '
    For iLp1 = iMkr To 0& Step -1&
        iJmp = iJumps(iLp1)
        For iLp2 = iJmp To iCnt - 1&
            iTmp = iLp2 - iJmp
            sCmp = s(iLp2 + iLbd)
            Do While sCmp < s(iTmp + iLbd)
                sSwp = s(iTmp + iJmp + iLbd)
                s(iTmp + iJmp + iLbd) = s(iTmp + iLbd)
                s(iTmp + iLbd) = sSwp
                iTmp = iTmp - iJmp
                If iTmp < 0& Then Exit Do
            Loop
            s(iTmp + iJmp + iLbd) = sCmp
            Next iLp2
      Next iLp1
End Sub

Public Function sRandomString(iLength As Integer) As String
    Dim i As Integer
    Dim j As Integer
    Dim s As String
    Static b As Boolean
    '
    If Not b Then
        Randomize
        b = True
    End If
    '
    Do Until j = iLength
        ' This returns an integer from 48 to 83.
        i = Int(36 * Rnd + 48)
        ' Skip over characters between 9 and A.
        If i > 57 Then i = i + 7
        ' Now, i is between 48 and 57 or 65 and 90.
        '                   "0"    "9"   "A"    "Z"
        s = s + Chr$(i)
        j = j + 1
    Loop
    sRandomString = s
End Function

I wonder (sort of hope not) if I'm sparking off a protracted discussion about sorts. Truth be told, I often just throw things into a ListBox, turn on "sorted", and then read them back out. I've always hoped that Microsoft knew how to do fast sorts.

Enjoy,
Elroy