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:

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

To do a bubble sort, you need three things:

- An indexed list or array with a sortable value or property
- 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
- 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.

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

…mrt

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).

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.

OK…ok…I’ll redo #29 with a quicksort and post it in a few days. Here’s a reference on all kinds of sorts (quick/heap/shaker etc) with code:

http://69.20.37.124/showthread.php?p=403676

From the folks over at Xtreme Visual Basic.

You guys sound like my old CS profs…;-)

…mrt

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.

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