count_sort_mod.c

/*
 * foo.c
 *
 *  Created on: Sep 27, 2010
 *      Author: wesley
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int max_elem(int* v, int n) {
    int i;
    int max = v[0];
    
    for (i = 0; i < n; i++) {
        if (max < v[i]) {
            max = v[i];
        }
    }
    
    return max;
}

void print_vector(int* v, int n) {
    int i;
    
    for (i = 0; i < n; i++) {
        printf(" %d", v[i]);
    }
    printf("\n");
}

void count_sort(int* v, int n) {
    int i, j;
    int max     = max_elem(v, n);
    int* temp   = (int*)malloc(sizeof(int) * n);
    
    memset(temp, 0, max);
    
    for(i = 0; i < n; i++) {
        temp[v[i]]++;
    }
    
    i = j = 0;
    
    for (i = 0; i < n; i++) {
        while (temp[j] == 0) j++;
        v[i] = j;
        temp[j]--;
    }
    
    free(temp);
}

int main(int argc, char** argv) {
    int v[10] = {9,8,7,6,5,4,3,2,1,0};
    
    print_vector(v, 10);
    count_sort(v, 10);
    print_vector(v, 10);
    
    return 0;
}