Results 1 to 13 of 13

20040115, 01:18 #1
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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,
Keyindexed 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>

20040115, 06:08 #2
 Join Date
 Feb 2001
 Location
 Silicon Valley, USA
 Posts
 23,112
 Thanks
 5
 Thanked 93 Times in 89 Posts
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.

20040115, 09:44 #3
 Join Date
 Nov 2001
 Location
 Arlington, Virginia, USA
 Posts
 1,394
 Thanks
 0
 Thanked 0 Times in 0 Posts
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 ReadyToRun 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 CDROM 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.

20040115, 09:55 #4
 Join Date
 Mar 2002
 Posts
 84,353
 Thanks
 0
 Thanked 18 Times in 18 Posts
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.

20040115, 15:16 #5
 Join Date
 Jan 2004
 Location
 Prague, Czech Republic
 Posts
 41
 Thanks
 0
 Thanked 0 Times in 0 Posts
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
MartinRegards,
Martin

20040115, 16:32 #6
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

20040115, 16:34 #7
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

20040115, 16:37 #8
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

20040116, 06:19 #9
 Join Date
 Feb 2001
 Location
 Silicon Valley, USA
 Posts
 23,112
 Thanks
 5
 Thanked 93 Times in 89 Posts
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>

20040116, 08:04 #10
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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 170348 milliseconds.

20040116, 11:20 #11
 Join Date
 Nov 2001
 Location
 Arlington, Virginia, USA
 Posts
 1,394
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

20040116, 17:52 #12
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

20040116, 22:35 #13
 Join Date
 Dec 2000
 Location
 New Hampshire, USA
 Posts
 3,386
 Thanks
 0
 Thanked 0 Times in 0 Posts
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>