|
=={{header|C++}}==
Uses C++11. Compile with
g++ -std=c++11 counting.cpp
<lang cpp>#include <algorithm>
#include <iterator>
#include <iostream>
#include <time.hvector>
template<typename ForwardIterator> void counting_sort(ForwardIterator begin,
//------------------------------------------------------------------------------
ForwardIterator end) {
using namespace std;
auto min_max = std::minmax_element(begin, end);
if (min_max.first == min_max.second) { // empty range
//------------------------------------------------------------------------------
const int MAX = 30return;
auto min = *min_max.first;
//------------------------------------------------------------------------------
auto max = *min_max.second;
class cSort
std::vector<unsigned> count((max - min) + 1, 0u);
{
for ( intauto i = mibegin; i <!= mxend; i++ i) {▼public:
++count[*i - min];
void sort( int* arr, int len )
{}
for ( intauto i = 0min; i < = lenmax; i++ i) {▼ int mi, mx, z = 0; findMinMax( arr, len, mi, mx );
int nlen = ( mxfor -(auto mij )= + 10; int*j temp< =count[i new- int[nlenmin]; ++j) {
*begin++ = i;
memset( temp, 0, nlen * sizeof( int ) );
for( int i = 0; i < len; i++ ) temp[arr[i] - mi]++;
▲ for( int i = mi; i <= mx; i++ )
{
while( temp[i - mi] )
{
arr[z++] = i;
temp[i - mi]--;
}
delete [] temp;
}
int main() {
private:
int a[] void= findMinMax({100, int*2, arr56, int200, len-52, int&3, mi99, int&33, mx177, )-199};
counting_sort(std::begin(a), std::end(a));
{
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
mi = INT_MAX; mx = 0;
std::cout << "\n";
▲ for( int i = 0; i < len; i++ )
{
if( arr[i] > mx ) mx = arr[i];
if( arr[i] < mi ) mi = arr[i];
}
};
//------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
srand( time( NULL ) ); int arr[MAX];
for( int i = 0; i < MAX; i++ )
arr[i] = rand() % 140 - rand() % 40 + 1;
for( int i = 0; i < MAX; i++ )
cout << arr[i] << ", ";
cout << endl << endl;
cSort s; s.sort( arr, MAX );
for( int i = 0; i < MAX; i++ )
cout << arr[i] << ", ";
cout << endl << endl;
return system( "pause" );
}
//------------------------------------------------------------------------------
</lang>
Output:
<pre>
-199 -52 2 3 33 56 99 100 177 200
105, -21, 20, 5, 3, 25, 101, 116, 82, 5, 88, 80, -9, 26, 62, 118, 131, -31, 3, 3
8, 40, -6, 46, 90, 7, 59, 104, 76, 12, 79,
-31, -21, -9, -6, 3, 3, 5, 5, 7, 12, 20, 25, 26, 38, 40, 46, 59, 62, 76, 79, 80,
82, 88, 90, 101, 104, 105, 116, 118, 131,
</pre>
|