Example: Sort Array by Frequency - qsort Approach in C

// Sort Array by Frequency - qsort Approach
#include <stdio.h>
#include <stdlib.h> // For qsort

// Structure to hold element and its frequency
struct ElementFreq {
    int value;
    int frequency;
};

// Custom comparison function for qsort
// It defines the sorting logic:
// 1. Sort by frequency in descending order
// 2. If frequencies are same, sort by value in ascending order
int compare(const void *a, const void *b) {
    struct ElementFreq *elemA = (struct ElementFreq *)a;
    struct ElementFreq *elemB = (struct ElementFreq *)b;

    // Compare frequencies first (descending order)
    if (elemA->frequency != elemB->frequency) {
        return elemB->frequency - elemA->frequency; // For descending frequency
    }
    // If frequencies are equal, compare values (ascending order)
    return elemA->value - elemB->value; // For ascending value
}

// Function to print the sorted array
void printSortedArray(struct ElementFreq freqArray[], int uniqueCount) {
    for (int i = 0; i < uniqueCount; i++) {
        for (int j = 0; j < freqArray[i].frequency; j++) {
            printf("%d ", freqArray[i].value);
        }
    }
    printf("\n");
}

int main() {
    // Step 1: Initialize the input array
    int arr[] = {2, 5, 2, 8, 5, 6, 8, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Create a temporary array of ElementFreq structs
    struct ElementFreq freqArray[n];
    int uniqueCount = 0;

    // Step 3: Count frequencies of each unique element
    for (int i = 0; i < n; i++) {
        int isPresent = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (freqArray[j].value == arr[i]) {
                freqArray[j].frequency++;
                isPresent = 1;
                break;
            }
        }
        if (!isPresent) {
            freqArray[uniqueCount].value = arr[i];
            freqArray[uniqueCount].frequency = 1;
            uniqueCount++;
        }
    }

    // Step 4: Sort the freqArray using qsort with the custom comparison function
    qsort(freqArray, uniqueCount, sizeof(struct ElementFreq), compare);

    // Step 5: Print the elements based on the sorted freqArray
    printf("Original array: ");
    for(int i=0; i<n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("Sorted by frequency: ");
    printSortedArray(freqArray, uniqueCount);

    return 0;
}