Printable View
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
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.
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
This is the basic:
https://www.youtube.com/watch?v=P00xJgWzz2c
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
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
Oh gosh, I guess I'll jump in. :)Quote:
Originally Posted by rdee
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.
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
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.
Maybe this will help
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:
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.Code:
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
Enjoy,
Elroy