Friday, October 25, 2013

Counting Sort Uva Example

For counting sort we assume that the numbers are in the range [0,k]. We set up a counter array which counts how many duplicates inside the input , and then reorder the output accordingly without any comparison at all.
Complexity O(n+k).

UVA problem:Age Sorting

Solution:

#include<iostream>
#include<stdio.h>

using namespace std;

int main(){

unsigned long long N,i,printnum;
int age,np[102];
while((scanf("%llu",&N))&&N){
    for(i=0;i<=100;i++){
        np[i]=0;
    }
    for(i=0;i<N;i++){
        cin>>age;
        np[age]++;
    }
    printnum=0;
    for(i=0;i<=100;i++){
    if(np[i]>0){
        for(int j=1;j<=np[i];j++){
            printf("%llu",i);
            printnum++;
            if(printnum<N) printf(" ");
        }

    }
    }
    printf("\n");

}
return 0;
}

No comments:

Post a Comment