8.2 Counting sort

<< Introduction to algorithms >> ( Second Edition )


8.2 Counting sort

Counting sort assumes that each of the n input elements is an integer in the range
0 to k, for some integer k. When k = O( n ), the sort runs in O( n ) time.
    The basic idea of counting sort is to determine, for each input element x, the
number of elements less than x. This information can be used to place element x
directly into its position in the output array. For example, if there are 17 elements
less than x, then x belongs in output position 18. This scheme must be modified
slightly to handle the situation in which several elements have the same value, since
we don't want to put them all in the same position.


Solution:

// 声明：本代码旨在实现原文的思想
// copyleft 2004    http://blog.csdn.net/mskia
// email:    [email protected]

#ifndef Counting_Sort_by_mskia
#define Counting_Sort_by_mskia

namespace te {
    void counting_sort( unsigned int *first , unsigned int *last ) {
        unsigned int max = 0;
        for ( unsigned  int *p = first; p <= last; ++p ) {
            if ( *p > max ) {
                max = *p;
            }
        }

        unsigned int len = max + 1;
        unsigned int *counter = new unsigned int [ len ];
        for ( unsigned int i = 0; i < len; ++i ) {
            counter[ i ] = 0;
        }

        for ( unsigned int *p = first; p <= last; ++p ) {
            ++counter[ *p ];
        }

        for ( unsigned int i = 0; i < len; ++i ) {
            unsigned int &t = counter[ i ];
            while ( t > 0 ) {
                *( first++ ) = i;
                --t;
            }
        }

        delete[] counter;

        return;
    }
}

#endif

本文地址：http://com.8s8s.com/it/it27057.htm