Re: A "valid" Bubble sort algorithm?

From: Randy Crawford (joe_at_burgershack.com)
Date: 03/11/04 

Date: Wed, 10 Mar 2004 18:09:49 -0600

Howard Kaikow wrote:
> Yes, I know that bubble sort is not worth (ab)using, but Ill ask this
> question anyway,
>
> Using Visual Basic the BubbleLong sub below is my attempt at encoding the
> bubble sort algorithm given by program 6.4 in Algorithms in C by Robert
> Sedegewick. The BubbleModLong sub below is from an unknown source and is
> much faster than the algorithm in program 6.4.
>
> However, the code in BubbleModLong looks suspect.
> Is it even a bubble sort?
> If not, anybody recognize the critter?
>
> Public Sub BubbleLong(a() As Long, L As Long, r As Long)
> ' Sedgewick 6.4
> Dim i As Long
> Dim j As Long
> Dim temp As Long
>
> For i = L To r - 1
> For j = r To i + 1 Step -1
> If a(j - 1) > a(j) Then
> temp = a(j)
> a(j) = a(j - 1)
> a(j - 1) = temp
> End If
> Next j
> Next i
> End Sub
>
> Public Sub BubbleModLong(a() As Long, L As Long, r As Long)
> ' Sedgewick 6.4, modified
> Dim i As Long
> Dim j As Long
> Dim temp As Long
>
> For i = L To r - 1
> For j = r To i + 1 Step -1
> If a(i) > a(j) Then
> temp = a(j)
> a(j) = a(i)
> a(i) = temp
> End If
> Next j
> Next i
> End Sub 

-- 
http://www.standards.com/; See Howard Kaikow's web site.
The way to tell if an algorithm is a bubblesort is:
1) does it iterate N*N times?  (where N is the number of items to sort)
2) does it immediately swap values after doing a compare?
If yes to both then it's a bubblesort.
A second implementation of a bubblesort should be no faster than the 
first, unless it, 1) reduces the number of comparisons, 2) it reduces 
the number of swaps, or it uses the CPU's hardware data caches better.
Remember, when comparing any pair of sorts, you need to run several 
different data sets through each implementation before you can know if 
it's really faster than an alternative.  In this case, try sending 
through 1) a set of random integers, 2) a set of forward sorted 
integers, 3) a set of reverse sorted integers.
I also recommend that you run several different sized input sets.  Using 
small, medium, and large sets will quickly reveal whether a sort is 
speeding up nicely or is speeding up more slowly than another sort.
Also make sure the data set is large enough to take several seconds to 
complete.  A 15 second run time is probably the minimum.  Below 5 
seconds is too short -- program startup and shutdown may have too great 
an impact on your run time to be accurate.
Finally, be sure to write a quick validation program (or function) that
verifies that your data is in fact correctly sorted.  There's no point 
in comparing a routine that's correct with one that isn't.
     Randy
-- 
Randy Crawford   http://www.ruf.rice.edu/~rand   rand AT rice DOT edu

Relevant Pages

  • Re: Returning Median Value
    ... That you are sorting singles does not make a great difference, the relative performance of the sorts in relation to each other remains the same and the absolute performance may be a little bit slower because comparing singles costs a little bit more than comparing longs. ... Max stack depth was set to 60 (which should be sufficient for up to 1 million elements to be sorted without resorting to insertion or heap sort in amlost all cases). ... Now if you can bear 4 ms for sorting 1000 items using bubble sort, ... Also the relative performance will change too, when the distribution of the items to be sorted changes. ...
    (microsoft.public.vb.general.discussion)
  • Re: Possible F77 Code Improvement ??
    ... In fact, it is probably the fastest sort, or at ... of bubble sort, heapsort and perhaps others. ... I can see how constructing the heap in this case requires only O ...
    (comp.lang.fortran)
  • Re: comparing sorts
    ... I think the bubble/insertion sort counters are right. ... real seconds for bubble is 1.60000008E-02 ... This puts the input array in sorted order. ... a wrong algorithm if you ignore that knowledge of your data. ...
    (comp.lang.fortran)
  • Re: comparing sorts
    ... You are doing only one simulation and basing your conclusions on that. ... Each time I do the sort, ... real seconds for bubble is 1.50000006E-02 ... real seconds for selection sort is 0.0000000 ...
    (comp.lang.fortran)
  • Re: Word Sorting
    ... Dim oRng As Word.Range ... Sub ArrangeAndSortNames() ... MsgBox "There is no valid selection to sort" ... Sub NumericalSuffixes(ByRef oRngSearch As Word.Range, ...
    (microsoft.public.word.docmanagement)