Bubble Sorts

Two problems so far, Eulers 22 and 29, have required sorts, at least for my implementations. Euler 22 sorts over 5000 name strings, and Euler 29 sorts nearly 10,000 numerics. In both cases I used a bubble sort. Bubble sorts get their name from the image of the greater-valued item “bubbling up” to its place in line.

Bubble sorts have some advantages and disadvantages. The BIG disadvantage is that no matter how nearly-sorted the list is at start, you will still go through it (n-1)^2 times, n being the number of items. The advantages of bubble sorts are:

  1. They’re easy to code. Typically just nine lines. And
  2. To make a descending sort, you reverse just one inequality

To do a bubble sort, you need three things:

  1. An indexed list or array with a sortable value or property
  2. Explicit or implicit knowledge of the count or quantity of items to sort. You may know the count (n) because you set it, or the computer knows it via Item.count or UBound(Item), for example
  3. A TEMP variable of the same type as being sorted, often also called SWAP

If you think of sorting a deck of cards, the outer loop sorts cards from 1 to 51, and the inner loop compares those values with cards from 2 to 52. With fast computers, bubble sorts are probably “fast enough.” Both problems for me took less than 20 seconds.

This is my implementation of a bubble sort. You’ll see it used in the next post, on Euler 22.

Sub BubbleItUp()   ‘an ascending sort

   Const n     As Long = 5
   Dim i       As Long
   Dim j       As Long
   Dim Char(n) As String * 1
   Dim TEMP    As String * 1
   For i = 1 To n
      Char(i) = CStr(n + 1 – i)
   Next i
   Debug.Print Char(1); Char(2); Char(3); Char(4); Char(5)
   For i = 1 To n – 1
      For j = i + 1 To n
         If Char(i) > Char(j) Then   ‘flip the inequality for a descending sort
           TEMP = Char(j)
            Char(j) = Char(i)
            Char(i) = TEMP
         End If
      Next j
      Debug.Print Char(1); Char(2); Char(3); Char(4); Char(5)
   Next i
End Sub


Posted in Uncategorized

4 thoughts on “Bubble Sorts

  1. Bubble sort. Ugh. As wikipedia says, “While simple, this algorithm is highly inefficient and is rarely used except in education”

    I’ll readily agree that it works, but surely we should make some room to attempt to produce a little elegance? Any of the algortihms that is O(n log n) for time and O(1) for memory (I get nervous about the stack for highly recursive sorts) would do. Heapsort isn’t hard to implement in VBA (I’m sure I have one somewhere).

  2. Michael, quicksort code is also short, but it runs up to 200x as fast as bubblesort.

    I sorted 10,000 random (long) numbers in 0.03 seconds vs 6 seconds with bubblesort.

  3. My post with a quicksort procedure hasn’t shown up, so I’ll try again. Note: using FORTRAN-like comparison operators to eliminate the hassles with angle brackets.

    Sub qsort( _
     v As Variant, _
     lft As Long, _
     rgt As Long, _
     Optional asc As Boolean = True _
    ‘assumes simple 1D arrays
    ‘defaults to ascending sort
     Dim j As Long, pvt As Long, t As Variant

      If lft .GE. rgt Then Exit Sub

      j = lft + Int((rgt – lft + 1) * Rnd)
      t = v(lft)
      v(lft) = v(j)
      v(j) = t

      pvt = lft

      For j = lft + 1 To rgt
        If IIf(asc, v(j) .LT. v(lft), v(j) .GT. v(lft)) Then
          pvt = pvt + 1
          t = v(pvt)
          v(pvt) = v(j)
          v(j) = t
        End If
      Next j

      t = v(lft)
      v(lft) = v(pvt)
      v(pvt) = t
      qsort v, lft, pvt – 1, asc
      qsort v, pvt + 1, rgt, asc
    End Sub

Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.