Results 1 to 13 of 13
  1. #1
    Gold Lounger
    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,
    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. #2
    Super Moderator jscher2000's Avatar
    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.

  3. #3
    Bronze Lounger
    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 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. #4
    Plutonium Lounger
    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.

  5. #5
    Lounger
    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
    Martin
    Regards,
    Martin

  6. #6
    Gold Lounger
    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.

  7. #7
    Gold Lounger
    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.

  8. #8
    Gold Lounger
    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.

  9. #9
    Super Moderator jscher2000's Avatar
    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>

  10. #10
    Gold Lounger
    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 170-348 milliseconds.

  11. #11
    Bronze Lounger
    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.

  12. #12
    Gold Lounger
    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.

  13. #13
    Gold Lounger
    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>


Posting Permissions

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