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