Fog Creek Software
Discussion Board




Which coding of Bubble Sort is faster?

Which method of coding Bubble Sort is better:

==================================

Do
    Swap = False
    For index = 1 To ItemCount - 1
      If Array(index - 1) > Array(index) Then
        temp = Array(index - 1)
        Array(index - 1) = Array(index)
        Array(index) = temp
        Swap = True
      End If
    Next index
Loop Until Swap = False

==============================

For i = LowerBound To UpperBound
  For j = LowerBound To UpperBound 
    If Array(j) > Array(i) Then     
      temp = Array(i)     
      Array(i) = Array(j)     
      Array(j) = temp     
    End If   
  Next j               
Next i

==============================

Someone told me to use the two - for loop - version because it's a lot faster.  I would think the one that exits after finding no swaps are necessary is faster.

F-16
Wednesday, February 25, 2004

No idea.
Why don't you add

Declare Function timeGetTime Lib "winmm.dll" () As Long

to you project, then you call timeGetTime() from your code, that'll return a big number representing the time elapsed since (a long time ago). Then you can calculate the elapsed time for both methods.

Yves
Wednesday, February 25, 2004

If you're concerned about speed why are you using a bubble sort?

veal
Wednesday, February 25, 2004

This one will not work:

For i = LowerBound To UpperBound
  For j = LowerBound To UpperBound
    If Array(j) > Array(i) Then   
      temp = Array(i)   
      Array(i) = Array(j)   
      Array(j) = temp   
    End If 
  Next j             
Next i

Either you meant an Selection Sort:

For i = 1 To N
  Array(i) = <find smallest element in Array(i .. N)>
Next i

Or you where trying to use the fact that after each complete loop the effect of bubble sort is putting the greatest element in the last position, so you can ignore it next:

For i = N To 2 Step -1
  For j = 2 to i
    If Array(j-1) > Array(j) Then Swap(j-1, j)
  Next j
Next i

This one can be changed to include a 'Changed' flag (as your first example). Both are O(N^2), but this second version of BubbleSort (with the 'Changed flag') shall, on average, do less comparisons but more swaps.

Either way, bubble-sort is not a real good option, even for 'simple algorithm you can throw fast' I recommed you remember Insertion Sort or, even better, Shell Sort.

Anyway, it would probably be better to use the built-in sorting routines (haven't used VB in a long time, but I guess it comes with a 'Sort' function, doesn't it?)

whatever
Wednesday, February 25, 2004

whatever: Sorting is really, really boring. Nobody should do it. It didn't suprise me though, that the source was listed in VB:

VB doesn't come with sorting routines! Unless, of course, you want to sort a list (UI) - which ends up being one of the workarounds I have seen on the net.

There are articles on writing sorting functions in VB, but general algorithms are hard to do since VB doesn't let you call a Pointer (whithout hacking). Functions can't be stored in variables and whoa - one of the many reasons I am trying to move as much of my developement to Python as possible :)

Sometimes it doesn't matter which algorithm to use, BTW. Don't optimize too early! You might be optimizing the wrong spot!

DarenThomas
Wednesday, February 25, 2004

This has got to be the funniest thread title ever.

Brian
Wednesday, February 25, 2004

Looks like someone was able to sneak a wireless-enabled laptop into their CompSci 101 midterm ;-)

Nigel
Wednesday, February 25, 2004

Here's a quicksort for VB that I have used in the past. I scalped if from someplace, but I can't give you a proper citation on the author... (I particularly like the use of While/Wend)

Public Sub QuickSort(vArray As Variant, L As Integer, R As Integer, Element As Integer, Optional SortAscending As Integer = 1)
     
    Dim i As Integer
    Dim j As Integer
    Dim k As Integer
    Dim X
    Dim Y
 
    Dim swaparray()
   
    ReDim swaparray(UBound(vArray))
   
    i = L
    j = R
    X = vArray(Element, (L + R) / 2)
 
    While (i <= j)
        If SortAscending = 1 Then
            While (vArray(Element, i) < X And i < R)
                i = i + 1
            Wend
       
            While (X < vArray(Element, j) And j > L)
                j = j - 1
            Wend
        Else
            While (vArray(Element, i) > X And i < R)
                i = i + 1
            Wend
       
            While (X > vArray(Element, j) And j > L)
                j = j - 1
            Wend
        End If
       
        If (i <= j) Then
            For k = LBound(vArray) To UBound(vArray)
                swaparray(k) = vArray(k, i)
            Next
            For k = LBound(vArray) To UBound(vArray)
                vArray(k, i) = vArray(k, j)
                vArray(k, j) = swaparray(k)
            Next
            i = i + 1
            j = j - 1
        End If
 
    Wend
   
    If (L < j) Then QuickSort vArray, L, j, Element, SortAscending
    If (i < R) Then QuickSort vArray, i, R, Element, SortAscending
Exit Sub


End Sub

The Plagarist
Wednesday, February 25, 2004

So finally we have the answer to "Why should I learn sorting algorithms?"

The answer: "Because I have to use VB and it doesn't come with one..."

=))

whatever
Wednesday, February 25, 2004

I'm with veal on this one. Why are you using a bubble sort for speed? Is this a homework question?

Dennis Atkins
Wednesday, February 25, 2004

Here's an article I found helpful with regards to sorting in VB, written by Francesco Balena:
http://www.vb2themax.com/HtmlDoc.asp?Table=Articles&ID=10

Sam Livingston-Gray
Wednesday, February 25, 2004

*  Recent Topics

*  Fog Creek Home