COMP1927 - Key Index Sort / Count Sort

Key Index Sorts are non-comparative. This means that instead of comparing elements to each other, elements are sorted using the 'key' as an index.'

For instance in a list of numbers where we know the range the numbers can be tallied using an array. Every time a number is encountered array[number] is incremented.

# Type

Non-Adaptive

Stability isn't an issue; ordering is ignored in a tally

In-Place

# Complexity

The lower bound of complexity is O(n) depending on what the key is.

# Example

# Code

void countSort (int array[], int length, int smallest, int biggest) { int tally = calloc(biggest-smallest, sizeof(int)); int i; for (i = 0; i < length; i++) { tally[array[i]]++; } int numSorted; int j; for (i = smallest; i < biggest; i++) { for (j = 0; j < tally[i]; j++) { array[numSorted] = i; numSorted++; } } }

page revision: 4, last edited: 09 Sep 2011 14:05