Sorting algorithms/Counting sort: Difference between revisions

countingSort(''array'', ''min'', ''max''):

''count'': '''array''' of (''max'' - ''min'' + 1) elements

initialize ''count'' with 0s

'''foreach''' ''number'' '''in''' ''array'':

''count''[''number'' - ''min''] := ''count''[''number'' - ''min''] + 1

'''end''' '''foreach'''

''z'' := 0

'''for''' ''i'' '''from''' ''min'' '''to''' ''max'':

'''while''' ( ''count''[''i'' - ''min''] > 0 )

''array''[''z''] := ''i''

''z'' := ''z'' + 1

''count''[''i'' - ''min''] := ''count''[''i'' - ''min''] - 1

'''end''' '''while'''

'''end''' '''for'''

'''end''' countingSort

'''Note''': we know that, given an array of integers, its maximum and minimum values can be always found; but if we imagine the worst case for an array of 32 bit integers, we see that in order to hold the counts, we need an array of 2³² elements, i.e. we need, to hold a count value up to 2³²-1, more or less 16 Gbytes. So the counting sort is more practical when the range is (very) limited and minimum and maximum values are known ''a priori''. (Anyway sparse arrays may limit the impact of the memory usage)

<lang AutoHotkey>

MsgBox % CountingSort("-1,1,1,0,-1",-1,1)

endfunction

</lang>

True

</lang>