Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.
Algorithm:
1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the input array. Store results in an array C.
2. The counting information stored in C can be used to determine the position of each element in the sorted array. Suppose we modify the values of the C [ j ] so that now C [ j ] = the number of keys less than or equal to j . Then we know that the elements with key “ j ” must be stored at the indices C [ j − 1 ]+ 1 ,…, C [ j ] of the final sorted array.
3. We use a “trick” to move the elements to the right position of an auxiliary array. Then we copy the sorted auxiliary array back to the original one.
The algorithm makes two passes over A and one pass over B. If size of the range k is smaller than size of input n, then time complexity=O(n). Also, note that it is a stable algorithm, meaning that ties are resolved by reporting those elements first which occur first.
void countSort(int * arr) { // The output array that will have sorted arr int output[ count( arr)]; // Create a count array to store count of individual element and // initialize count array as 0 int count[RANGE + 1], i; memset(count, 0, sizeof(count)); // Store count of each element for(i = 0; arr[i]; ++i) ++count[ arr[i]]; /* modified count array indicates the position of each object in the output sequence. */ for (i = 1; i <= RANGE; ++i) count[i] += count[i-1]; // Build the output array for (i = 0; arr[i]; ++i) { output[count[ arr[i]]-1] = arr[i]; --count[ arr[i]]; } // Copy the output array to arr for (i = 0; arr[i]; ++i) arr[i] = output[i]; }
Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)
Source: Counting Sort
Algorithm is fine. But where can I get its program in c.
See this : best c compiler for windows
i dont understand what 4th line meaning can admin explain