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.
F16
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(j1) > Array(j) Then Swap(j1, 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, bubblesort 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 builtin 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 wirelessenabled 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 LivingstonGray
Wednesday, February 25, 2004
Recent Topics
Fog Creek Home
