Example: Sort Array by Frequency - Approach 1

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

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

// Comparison function for qsort
// Sorts by frequency (descending)
// If frequencies are equal, sorts by value (ascending)
int compareElementFrequency(const void *a, const void *b) {
    ElementFrequency *efA = (ElementFrequency *)a;
    ElementFrequency *efB = (ElementFrequency *)b;

    // Primary sort: frequency (descending)
    if (efA->frequency != efB->frequency) {
        return efB->frequency - efA->frequency;
    }
    // Secondary sort: value (ascending) if frequencies are equal
    return efA->value - efB->value;
}

// Function to sort array by frequency
void sortByFrequency(int arr[], int n) {
    // Step 1: Count frequencies of each element
    // We'll use a temporary array of ElementFrequency structs
    // This is an inefficient way to count frequencies for large or sparse ranges
    // but works for demonstration. Better would be a hash map or sorting first.
    // For simplicity, we assume elements are within a reasonable range for demonstration.
    // A more robust frequency counting involves sorting the input array first or using a hash map.

    // Let's optimize frequency counting by first sorting the input array
    // This groups identical elements together, making frequency counting easier.
    qsort(arr, n, sizeof(int), [](const void* a, const void* b){
        return *(int*)a - *(int*)b;
    });

    ElementFrequency *freqArray = (ElementFrequency *)malloc(n * sizeof(ElementFrequency));
    if (freqArray == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }

    int uniqueCount = 0;
    if (n > 0) {
        freqArray[uniqueCount].value = arr[0];
        freqArray[uniqueCount].frequency = 1;
        uniqueCount++;

        for (int i = 1; i < n; i++) {
            if (arr[i] == arr[i-1]) {
                freqArray[uniqueCount-1].frequency++;
            } else {
                freqArray[uniqueCount].value = arr[i];
                freqArray[uniqueCount].frequency = 1;
                uniqueCount++;
            }
        }
    }

    // Step 2: Sort the freqArray based on frequency and then value
    qsort(freqArray, uniqueCount, sizeof(ElementFrequency), compareElementFrequency);

    // Step 3: Reconstruct the original array with sorted elements
    int k = 0;
    for (int i = 0; i < uniqueCount; i++) {
        for (int j = 0; j < freqArray[i].frequency; j++) {
            arr[k++] = freqArray[i].value;
        }
    }

    free(freqArray); // Free allocated memory
}

int main() {
    int arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    sortByFrequency(arr, n);

    printf("Sorted by frequency: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // Another example
    int arr2[] = {1, 1, 1, 2, 2, 3};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    printf("\nOriginal array 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\n");

    sortByFrequency(arr2, n2);

    printf("Sorted by frequency 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\n");

    return 0;
}