The Old Joel on Software Forum: Part 4 (of 5) - Which coding of Bubble Sort is faster?

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