YoungProgrammer

Lesson: 21
Problem: 10062
Title: Tell me the frequencies!
Difficulty Level: 2.5
Date: FEB 2, 2009
Site: UVA

Given a string, you have to sort the character by frequency. To solve 

this problem, you have to know how to sort an array of struct type.

Consider the first sample input: AAABBC

A has frequency of 3
B has frequency of 2
C has frequency of 1

We know A's ASCII = 65, B's ASCII = 66 and C's ASCII = 67, so output is:
67 1  as C( 67) has thelowest frequency.
66 2
65 3

Cosider another example: AAABBBCC
Here, B and A has same frequency, But B's ASICC > A's ASCII, so B will 

come first.
Output:
67 1
66 2
65 3

Another example:
ABCDEF
Output:
70 1
69 1
68 1
67 1
66 1
65 1 

Because: If two characters are present the same time print the 

information of the ASCII character with higher ASCII value first

Source Code:
#include<stdio.h>
#include<stdlib.h>

char input[1002]; //input length maximum 1000

struct ss {
    int ASCII;
    int fre;
};

ss FRE[350];

int comp(const void *a, const void *b) { 
    ss *x = (ss *)a;
    ss *y = (ss *)b;
    if(x->fre != y->fre) { // if frequency is not same, then  we sort 

the array based on frequency
        return x->fre-y->fre; // ascending order
    }
    return y->ASCII-x->ASCII;
	// if frequency is same, then we sort the array according to the 

ascii value, descending order
    return 0;
}

void CountFre() {
    int i, ascii;
    for(i = 0; input[i]; i++) {
        ascii = input[i];
        FRE[ascii].ASCII = ascii;
        FRE[ascii].fre++;
    }
    qsort(&FRE,256,sizeof(ss),comp); // most important, using library 

quick sort function
}

void Print() {
    int i, j = 1;
    for(i = 0; i<=255; i++) {
        if(FRE[i].fre == 0) continue; // not in the input
        printf("%d %d\n",FRE[i].ASCII,FRE[i].fre);
        FRE[i].fre = 0; // making clear the frequency after printing for 

the next test case.
    }
}

int main() {
    int kase = 0;
    while(gets(input)) { // read until end of the file
        CountFre();
        if(kase++) puts(""); // printing a blank line between two cases
        Print();
    }
    return 0;
}