Wikibooks: Algorithm Implementation/Sorting/Counting sort

• Format: Book
• Language: English
• Subjects: The Pointers
• Online Access: https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Counting_sort

wikipedia Counting sort = = / end is the last index + 1 / void csort(int array[] const int end const int max const int min) { int i const int range = max min+1 int count[range+1] scratch[end] for(i=0 i =0 i ) { int c = array[i] min int s = count[c] scratch[s] = array[i] / Increment count so that the next element with the same value as the current element is placed into its own position in scratch. / count[c]++ } for(i=0 i = = #include #include / To sort a sequence using an integer key having a known range you must define a function object that given an element returns a zero based key. The sorting is performed by calling the counting sort function template passing to it the sequence extremes the maximum number of keys and the function object. If the sorted sequence must anyway be copied to another sequence it is more efficient to call the counting sort copy function template passing to it the above arguments plus a pointer or iterator at the beginning of the destination sequence. If this algorithm must be called several times it is further more efficient to call the counting sort copy with counters function templates passing to it the above arguments plus a pointer or iterator to the beginning of the auxiliary buffer used by the algorithm. / / Function template counting sort copy with counters . Input The sequence to sort between the pointers or bidirectional iterator begin to sort and end to sort . The sequence in which to copy the sorted elements beginning at the address referenced by the pointer or random iterator sorted and having as many elements as the sequence to sort The sequence in which to store the temporary counters beginning at the address referenced by the pointer or random iterator counters and containing n keys elements. The maximum number of keys n keys . The function object get key that for any element of the sequence returns its key as an ingeger number in the range [0 n keys 1]. Output The sequence beginning at the address referenced by sorted sorted by the key. Example of usage where it is ...