#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR 256
// Structure to store character frequency
struct CharFreq {
char character;
int frequency;
};
// Function to compare two character frequencies
int compare(const void* a, const void* b) {
return ((struct CharFreq*)b)->frequency - ((struct CharFreq*)a)->frequency;
}
// Function to sort string in descending order based on character frequency
void sortString(char* s) {
// Create an array to store character frequencies
struct CharFreq freq[MAX_CHAR] = {{0, 0}};
// Count frequencies of characters in the string
int length = strlen(s);
for (int i = 0; i < length; i++) {
freq[s[i]].character = s[i];
freq[s[i]].frequency++;
}
// Sort the array based on character frequency
qsort(freq, MAX_CHAR, sizeof(struct CharFreq), compare);
// Construct the sorted string
int index = 0;
for (int i = 0; i < MAX_CHAR; i++) {
while (freq[i].frequency--) {
s[index++] = freq[i].character;
}
}
}
int main() {
char s[] = "tree"; // Example string
printf("Original string: %s\n", s);
sortString(s);
printf("String sorted in descending order of frequency: %s\n", s);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKI2RlZmluZSBNQVhfQ0hBUiAyNTYKCi8vIFN0cnVjdHVyZSB0byBzdG9yZSBjaGFyYWN0ZXIgZnJlcXVlbmN5CnN0cnVjdCBDaGFyRnJlcSB7CiAgICBjaGFyIGNoYXJhY3RlcjsKICAgIGludCBmcmVxdWVuY3k7Cn07CgovLyBGdW5jdGlvbiB0byBjb21wYXJlIHR3byBjaGFyYWN0ZXIgZnJlcXVlbmNpZXMKaW50IGNvbXBhcmUoY29uc3Qgdm9pZCogYSwgY29uc3Qgdm9pZCogYikgewogICAgcmV0dXJuICgoc3RydWN0IENoYXJGcmVxKiliKS0+ZnJlcXVlbmN5IC0gKChzdHJ1Y3QgQ2hhckZyZXEqKWEpLT5mcmVxdWVuY3k7Cn0KCi8vIEZ1bmN0aW9uIHRvIHNvcnQgc3RyaW5nIGluIGRlc2NlbmRpbmcgb3JkZXIgYmFzZWQgb24gY2hhcmFjdGVyIGZyZXF1ZW5jeQp2b2lkIHNvcnRTdHJpbmcoY2hhciogcykgewogICAgLy8gQ3JlYXRlIGFuIGFycmF5IHRvIHN0b3JlIGNoYXJhY3RlciBmcmVxdWVuY2llcwogICAgc3RydWN0IENoYXJGcmVxIGZyZXFbTUFYX0NIQVJdID0ge3swLCAwfX07CgogICAgLy8gQ291bnQgZnJlcXVlbmNpZXMgb2YgY2hhcmFjdGVycyBpbiB0aGUgc3RyaW5nCiAgICBpbnQgbGVuZ3RoID0gc3RybGVuKHMpOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBsZW5ndGg7IGkrKykgewogICAgICAgIGZyZXFbc1tpXV0uY2hhcmFjdGVyID0gc1tpXTsKICAgICAgICBmcmVxW3NbaV1dLmZyZXF1ZW5jeSsrOwogICAgfQoKICAgIC8vIFNvcnQgdGhlIGFycmF5IGJhc2VkIG9uIGNoYXJhY3RlciBmcmVxdWVuY3kKICAgIHFzb3J0KGZyZXEsIE1BWF9DSEFSLCBzaXplb2Yoc3RydWN0IENoYXJGcmVxKSwgY29tcGFyZSk7CgogICAgLy8gQ29uc3RydWN0IHRoZSBzb3J0ZWQgc3RyaW5nCiAgICBpbnQgaW5kZXggPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBNQVhfQ0hBUjsgaSsrKSB7CiAgICAgICAgd2hpbGUgKGZyZXFbaV0uZnJlcXVlbmN5LS0pIHsKICAgICAgICAgICAgc1tpbmRleCsrXSA9IGZyZXFbaV0uY2hhcmFjdGVyOwogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBjaGFyIHNbXSA9ICJ0cmVlIjsgLy8gRXhhbXBsZSBzdHJpbmcKICAgIHByaW50ZigiT3JpZ2luYWwgc3RyaW5nOiAlc1xuIiwgcyk7CiAgICBzb3J0U3RyaW5nKHMpOwogICAgcHJpbnRmKCJTdHJpbmcgc29ydGVkIGluIGRlc2NlbmRpbmcgb3JkZXIgb2YgZnJlcXVlbmN5OiAlc1xuIiwgcyk7CiAgICByZXR1cm4gMDsKfQo=