# Thread: Sorting algorithms: Counting sort (VB/VBA)

1. ## Sorting algorithms: Counting sort (VB/VBA)

I am doing some testing of various sorting algorithms using VB 6, so I decided to implement some of the algorithms
in Robert Sedgewick's book Algorithms in C.

The first question that arises is "How accurately does my VB implementation follow Sedgewick's algorithm?".

In some cases, I found improvements on his algorithms. Perhaps, an interesting case is Program 6.17,
Key-indexed counting, on page 300 of Sedgewick's book.

My code produces correct sorts, but is it a faithful implementation of his algorithm?

I then noticed two things:

1. His algorithm seemed inefficient, so I made a simple change that more than doubled the speed.

2. I already had an implementation of counting sort that used less memory, but a slight performance hit,
tho still twice as fast as Program 6.17.

Using 3 samples of 10 000 000 random Longs with values from 0 to 999 on a Pentium II 400 with 768MB of memory:

My implementation of Program 6.17 used an average of 5293 milliseconds for the 3 runs (total time 15879 milliseconds).

My improved implementation of Program 6.7 used an average of 2096 milliseconds for the 3 runs (total time 6290 milliseconds).

My improved, reduced memory, implementation of Program 6.7 used an average of 2237 milliseconds for the 3 runs (total time 6712 milliseconds).

I am posting the code for each below.
Anybody see any errors?

<pre>Public Sub KeyIndexedCountingLong(a() As Long, ByVal L As Long, ByVal r As Long)
' Sedgewick 6.17
Dim i As Long
Dim j As Long
Dim m As Long
Dim lngPtr As Long

ReDim B(r - L + 1) As Long

m = a(L)
For i = L To r
If a(i) > m Then
m = a(i)
End If
Next i
m = m + 1
ReDim cnt(m) As Long

For j = 0 To m - 1
cnt(j) = 0
Next j
For i = L To r
lngPtr = a(i) + 1
cnt(lngPtr) = cnt(lngPtr) + 1
Next i

For j = 1 To m - 1
cnt(j) = cnt(j) + cnt(j - 1)
Next j
For i = L To r
lngPtr = cnt(a(i))
B(lngPtr) = a(i)
cnt(a(i)) = lngPtr + 1
Next i
For i = L To r
a(i) = B(i)
Next i
End Sub

Public Sub HKKeyIndexedCountingLong(a() As Long)
' Sedgewick 6.17, modified
Dim i As Long
Dim j As Long
Dim m As Long
Dim r As Long
Dim lngPtr As Long

m = a(0)
r = UBound(a)
For i = 0 To r
If a(i) > m Then
m = a(i)
End If
Next i
ReDim cnt(m) As Long

For j = 0 To m
cnt(j) = 0
Next j
For i = 0 To r
lngPtr = a(i)
cnt(lngPtr) = cnt(lngPtr) + 1
Next i

lngPtr = 0
For i = 0 To m
For j = 1 To cnt(i)
a(lngPtr) = i
lngPtr = lngPtr + 1
Next j
Next i
End Sub

Public Sub CountingSort(lngData() As Long)
Dim lngArrayIndex As Long
Dim lngCounts() As Long
Dim lngI As Long
Dim lngJ As Long
Dim lngMaximumValue As Long
Dim lngMinimumValue As Long
Dim lngTop As Long
Dim lngValue As Long

lngArrayIndex = UBound(lngData)
lngMinimumValue = lngData(0)
lngMaximumValue = lngMinimumValue
For lngI = 0 To lngArrayIndex
lngValue = lngData(lngI)
If lngValue < lngMinimumValue Then
lngMinimumValue = lngValue
ElseIf lngValue > lngMaximumValue Then
lngMaximumValue = lngValue
End If
Next lngI

lngTop = lngMaximumValue - lngMinimumValue
ReDim lngCounts(lngTop)

For lngI = 0 To lngTop
lngCounts(lngI) = 0
Next lngI

For lngI = 0 To lngArrayIndex
lngValue = lngData(lngI) - lngMinimumValue
lngCounts(lngValue) = lngCounts(lngValue) + 1
Next lngI

lngArrayIndex = 0
For lngI = 0 To lngTop
lngValue = lngI + lngMinimumValue
For lngJ = 1 To lngCounts(lngI)
lngData(lngArrayIndex) = lngValue
lngArrayIndex = lngArrayIndex + 1
Next lngJ
Next lngI
End Sub
</pre>

2. ## Re: Sorting algorithms: Counting sort (VB/VBA)

I don't know enough about C to say whether the 6.17 code makes sense in that context. However, because it gives an error for negative numbers, the VB translation doesn't appear to be the most general approach, quite apart from its (lack of) efficiency.

3. ## Re: Sorting algorithms: Counting sort (VB/VBA)

Not being familiar with the Sedgewick book (or with C) I can't answer the question, this is just a comment - most algorithm texts I've seen are oriented towards C/C++ languages, but a good reference that covers algorithms in VB is Ready-To-Run Visual Basic Algorithms by Rod Stephens. The chapter on sorting includes sample algorithms for Bubblesort, Quicksort, Mergesort, Heapsort, Countingsort, Bucketsort, etc., and discussion of which algorithm is most efficient under different circumstances. Other chapters include algorithms for working with Lists, Stacks & Queues, Arrays, Recursion, Trees, Searching, Hashing, etc. The book includes a CD-ROM with sample code.

You may or may not be already be familiar with this book, I thought it was worth mentioning because it is hard to find a good algorithm text that doesn't require "translation" from C or another language to be able to use the code in VB.

4. ## Re: Sorting algorithms: Counting sort (VB/VBA)

If the difference between the minimum and maximum value of the items in the array to be sorted is large, these algorithms will use a horrible amount of memory. If the items can vary over the entire range of long integers, you'd need an array of over 4 billion longs, i.e. 16 gigabyte! In that case, algorithms that sort an array in place, such as QuickSort or ShellSort, are much better. But if the range is small, these algoritms are very fast.

5. ## Re: Sorting algorithms: Counting sort (VB/VBA)

Hello Mark,
I am rather working with VBA. Is this book also for me then? I searched inside on Amazon and it seems so...
Thanks
Martin

6. ## Re: Sorting algorithms: Counting sort (VB/VBA)

The algorithm is not intended to work with negative numbers, tho the code could be faked out to do so.

7. ## Re: Sorting algorithms: Counting sort (VB/VBA)

I'm familiar with the book, and it is a useful read, but not all of the algorithms presented are efficient, so take care in using code in te book.

8. ## Re: Sorting algorithms: Counting sort (VB/VBA)

Yes, that's known charcteristic of the algorithm.

A sorting algorithm needs to be chosen in view of its intended use.

9. ## Re: Sorting algorithms: Counting sort (VB/VBA)

This one seems most adapted to electronic voting. I guess we better test it thoroughly. <img src=/S/laugh.gif border=0 alt=laugh width=15 height=15>

10. ## Re: Sorting algorithms: Counting sort (VB/VBA)

On a Pentium II 400 with 768MB memory, using 100000 Long data type with values allowed from 0 to 123456789.

4 variants of "Counting sort" used 14834 to 21360 milliseconds.

12 variants of "QucickSort" used 170-348 milliseconds.

11. ## Re: Sorting algorithms: Counting sort (VB/VBA)

Thanx for the warning - I don't have a background in Computer Science (I wuz an English major in college) so found the book useful. Some C/C++ elitists would probably assert that the term "efficient algorithm" used in conjunction with "Visual Basic" is an oxymoron.

12. ## Re: Sorting algorithms: Counting sort (VB/VBA)

Lemmeee clarify.

Rod's book is worth having.
He does include a not so good implementation of a particular algorithm, but that is not uncommon, I've seen worse in well known Excel and Access VBA books.
I am going to release a demonstration of this in the, hopefully, not too distant future.

13. ## Re: Sorting algorithms: Counting sort (VB/VBA)

Here's more info to demonstrate that one must take care in choosing among implementations of sorting algorithms.
The same 10 implementations of variants of quicksort were used in both cases.

<pre>Quick Sort(Start: 1:47:06 on 16 Jan 2004)
Data type: Long
Display data: No
Maximum integer value: 999
Number of data items: 10000000
Number of samples: 1
Order of source data: Random
Reuse data: No
Set randomize seed: Yes
Source: Array
Target: Array
Use integer data: Yes
Quick Sort(0): 23177 milliseconds
Quick Sort(1): 21398 milliseconds
Quick Sort(2): 23349 milliseconds
Quick Sort(3): 22619 milliseconds
Quick Sort(4): 13982 milliseconds
Quick Sort(5): 22715 milliseconds
Quick Sort(6): 22544 milliseconds
Quick Sort(7): 22913 milliseconds
Quick Sort(8): 31250 milliseconds
Quick Sort(9): (OUT_OF_STACK_SPACE)
Quick Sort(End: 1:50:59 on 16 Jan 2004, timed/elapsed: 203952/232808 milliseconds, 87.61%)
Quick Sort(Start: 1:51:46 on 16 Jan 2004)
Data type: Long
Display data: No
Maximum integer value: 999
Number of data items: 5000000
Number of samples: 1
Order of source data: Random
Reuse data: No
Set randomize seed: Yes
Source: Array
Target: Array
Use integer data: Yes
Quick Sort(0): 11018 milliseconds
Quick Sort(1): 10267 milliseconds
Quick Sort(2): 11013 milliseconds
Quick Sort(3): 10832 milliseconds
Quick Sort(4): 6887 milliseconds
Quick Sort(5): 10589 milliseconds
Quick Sort(6): 10795 milliseconds
Quick Sort(7): 10983 milliseconds
Quick Sort(8): 15112 milliseconds
Quick Sort(9): 548878 milliseconds
Quick Sort(End: 2:02:44 on 16 Jan 2004, timed/elapsed: 646380/658530 milliseconds, 98.15%)
</pre>

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•