Count Sort, a special case of indexed sort

CountSort is yet another sort algorithm, which can be applied only under very particular conditions but that, when such conditions are met, turns to be the fastest of the lot. Count Sort can be used when the key is of Integer type, or when it is of Long type but the range of values is not too large.

The idea underlying the algorithm is that each key data can indirectly work an initial index for itself. The routine parses the original array determining its minimum and maximum value, then builds a temporary array of Long with one element for each possible value of the key. The routine parses the original array again, this time counting the occurrences of each distinct value. After this step, it is very easy to evaluate where each value has to go in the definitive, sorted array, and this can be accomplished in the third step. Here is the complete routine:

Sub NdxCountSortI(arr() As Integer, ndx() As Long, Optional ByVal numEls As _    Variant)    Dim index As Long    Dim inverseOrder As Boolean    Dim value As Integer    Dim minValue As Integer    Dim maxValue As Integer    Dim saveCount As Integer    Dim newIndex As Long    ' account for optional arguments    If IsMissing(numEls) Then numEls = UBound(arr)    ' search min and max value    minValue = arr(LBound(arr))    maxValue = minValue    For index = LBound(arr) To numEls        value = arr(index)        If value < minValue Then            minValue = value        ElseIf value > maxValue Then            maxValue = value        End If    Next    ' declare the temporary index arr    ReDim Count(minValue To maxValue) As Long    ' fill each item of the temporary arr with    ' number of occurrences for that value    For index = LBound(arr) To numEls        value = arr(index)        Count(value) = Count(value) + 1    Next    ' parse the count() array to replace the count    ' value with the definitive position    ' in the sorted array    newIndex = LBound(ndx)    For index = minValue To maxValue        saveCount = Count(index)        Count(index) = newIndex        newIndex = newIndex + saveCount    Next    ' finally build the index    For index = LBound(arr) To numEls    ' get position of the item in the index        newIndex = Count(arr(index))        ' remember the original position        ndx(newIndex) = index        ' next time store value in subsequent item        Count(arr(index)) = newIndex + 1    NextEnd Sub

The most interesting detail on this sorting algorithm is that its total time is proportional to the number of items to be sorted, therefore is even more convenient than Quick Sort, whose processing time grows proportionally to N * Log2(N). When sorting 10,000 items, Count Sort is 2.5 faster than Quick Sort, and is about five times faster when sorting one hundred thousand values.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

The Latest

microsoft careers

Top Careers at Microsoft

Microsoft has gained its position as one of the top companies in the world, and Microsoft careers are flourishing. This multinational company is efficiently developing popular software and computers with other consumer electronics. It is a dream come true for so many people to acquire a high paid, high-prestige job

your company's audio

4 Areas of Your Company Where Your Audio Really Matters

Your company probably relies on audio more than you realize. Whether you’re creating a spoken text message to a colleague or giving a speech, you want your audio to shine. Otherwise, you could cause avoidable friction points and potentially hurt your brand reputation. For example, let’s say you create a

chrome os developer mode

How to Turn on Chrome OS Developer Mode

Google’s Chrome OS is a popular operating system that is widely used on Chromebooks and other devices. While it is designed to be simple and user-friendly, there are times when users may want to access additional features and functionality. One way to do this is by turning on Chrome OS