1.1 Binary file sorting/key_indexed_counting/key_indexed_counting has changed

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/sorting/key_indexed_counting/key_indexed_counting.cpp	Thu May 14 19:50:23 2015 -0500
     2.3 @@ -0,0 +1,93 @@
     2.4 +#include <cerrno>
     2.5 +#include <cstdlib>
     2.6 +#include <cstring>
     2.7 +#include <fstream>
     2.8 +#include <iostream>
     2.9 +#include <sstream>
    2.10 +#include <string>
    2.11 +#include <vector>
    2.12 +
    2.13 +typedef std::pair<int, std::string> key_value_pair;
    2.14 +typedef std::vector< key_value_pair > pair_vector;
    2.15 +
    2.16 +
    2.17 +void key_indexed_counting_sort ( int R, pair_vector &data ) {
    2.18 +    int N = data.size();
    2.19 +    pair_vector aux(N);
    2.20 +    int count[R+1];
    2.21 +
    2.22 +    for (int i = 0; i < R+1; ++i ) {
    2.23 +        count[i] = 0;
    2.24 +        }
    2.25 +
    2.26 +    // Compute frequency counts
    2.27 +    for ( int i = 0; i < N; ++i ) {
    2.28 +        count[ data[i].first + 1 ]++;
    2.29 +        }
    2.30 +
    2.31 +    // Transform counts to indices
    2.32 +    for ( int r = 0; r < R; ++r ) {
    2.33 +        count[ r+1 ] += count[ r ];
    2.34 +        }
    2.35 +
    2.36 +    // Distribute the records
    2.37 +    for ( int i = 0; i < N; ++i ) {
    2.38 +        aux[ count[ data[i].first ]++ ] = data[i];
    2.39 +        }
    2.40 +
    2.41 +    // Copy back
    2.42 +    for ( int i = 0; i < N; ++i ) {
    2.43 +        data[i] = aux[i];
    2.44 +        }
    2.45 +    }
    2.46 +
    2.47 +int main ( int argc, char **argv ) {
    2.48 +    if ( argc != 2 ) {
    2.49 +        std::cerr << "Usage: key_indexed_counting DATAFILE" << std::endl;
    2.50 +        exit( EXIT_FAILURE );;
    2.51 +        }
    2.52 +
    2.53 +    std::ifstream file( argv[1] );
    2.54 +    if ( ! file.is_open() ) {
    2.55 +        std::cerr << "Unable to open file " << argv[1] << ": " << errno << " " << strerror( errno ) << std::endl;
    2.56 +        exit( EXIT_FAILURE );
    2.57 +        }
    2.58 +
    2.59 +    int R = 0;
    2.60 +    const int MAX_LINE = 80;
    2.61 +    char s[MAX_LINE + 1];
    2.62 +
    2.63 +    file.getline( s, MAX_LINE );
    2.64 +    R = strtol( s, NULL, 10 );
    2.65 +    std::cout << "R is " << R << std::endl;
    2.66 +
    2.67 +    pair_vector data;
    2.68 +
    2.69 +    while ( file.good() ) {
    2.70 +        file.getline( s, MAX_LINE );
    2.71 +
    2.72 +        std::string buf;
    2.73 +        std::stringstream ss( s );
    2.74 +        std::vector<std::string> parts;
    2.75 +        while ( ss >> buf )
    2.76 +            parts.push_back( buf );
    2.77 +
    2.78 +        if ( parts.size() == 2 ) {
    2.79 +            int key = strtol( parts[1].c_str(), NULL, 10 );
    2.80 +            data.push_back( std::make_pair( key, parts[0] ) );
    2.81 +            }
    2.82 +        }
    2.83 +
    2.84 +    for ( auto it = data.begin(); it != data.end(); ++it ) {
    2.85 +        std::cout << (*it).first << " " << (*it).second << std::endl;
    2.86 +        }
    2.87 +    std::cout << std::endl;
    2.88 +
    2.89 +    key_indexed_counting_sort( R, data );
    2.90 +
    2.91 +    for ( auto it = data.begin(); it != data.end(); ++it ) {
    2.92 +        std::cout << (*it).first << " " << (*it).second << std::endl;
    2.93 +        }
    2.94 +
    2.95 +    exit( EXIT_SUCCESS );
    2.96 +    }

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/sorting/key_indexed_counting/students.txt	Thu May 14 19:50:23 2015 -0500
     3.3 @@ -0,0 +1,21 @@
     3.4 +4
     3.5 +Anderson        2
     3.6 +Brown   3
     3.7 +Davis   3
     3.8 +Garcia  4
     3.9 +Harris  1
    3.10 +Jackson 3
    3.11 +Johnson 4
    3.12 +Jones   3
    3.13 +Martin  1
    3.14 +Martinez        2
    3.15 +Miller  2
    3.16 +Moore   1
    3.17 +Robinson        2
    3.18 +Smith   4
    3.19 +Taylor  3
    3.20 +Thomas  4
    3.21 +Thiompson       4
    3.22 +White   2
    3.23 +Williams        3
    3.24 +Wilson  4