Example: Sort Array by Frequency - Approach 2

// Sort Array by Frequency - Approach 2
#include <stdio.h>
#include <stdlib.h> // For qsort and malloc
#include <limits.h> // For INT_MIN, INT_MAX (or just set a MAX_VAL)

// Structure to hold element value and its frequency (same as Approach 1)
typedef struct {
    int value;
    int frequency;
} ElementFrequency;

// Comparison function for qsort (same as Approach 1)
int compareElementFrequency_2(const void *a, const void *b) {
    ElementFrequency *efA = (ElementFrequency *)a;
    ElementFrequency *efB = (ElementFrequency *)b;

    if (efA->frequency != efB->frequency) {
        return efB->frequency - efA->frequency; // Descending frequency
    }
    return efA->value - efB->value; // Ascending value for ties
}

// Function to sort array by frequency using auxiliary frequency array
void sortByFrequencyLimitedRange(int arr[], int n, int max_val_in_arr) {
    if (n == 0) return;

    // Step 1: Use an auxiliary array to count frequencies
    // The size of this array depends on the maximum possible value in arr.
    // For demonstration, let's assume max_val_in_arr is known.
    // In a real scenario, you'd find the max value in the array first.
    int *freq_map = (int *)calloc(max_val_in_arr + 1, sizeof(int));
    if (freq_map == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }

    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0 && arr[i] <= max_val_in_arr) { // Ensure value is within bounds
            freq_map[arr[i]]++;
        }
    }

    // Step 2: Create an array of ElementFrequency structs from the frequency map
    ElementFrequency *freqArray = (ElementFrequency *)malloc((max_val_in_arr + 1) * sizeof(ElementFrequency));
    if (freqArray == NULL) {
        printf("Memory allocation failed.\n");
        free(freq_map);
        return;
    }

    int uniqueCount = 0;
    for (int i = 0; i <= max_val_in_arr; i++) {
        if (freq_map[i] > 0) {
            freqArray[uniqueCount].value = i;
            freqArray[uniqueCount].frequency = freq_map[i];
            uniqueCount++;
        }
    }

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

    // Step 4: 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(freq_map);
    free(freqArray);
}

int main() {
    int arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_val = 12; // Assuming max value is 12 for this example.
                      // In a real scenario, you'd find this dynamically.

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

    sortByFrequencyLimitedRange(arr, n, max_val);

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

    // Another example
    int arr3[] = {7, 1, 5, 1, 7, 7, 5, 1, 2};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int max_val3 = 7; // Max value in arr3

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

    sortByFrequencyLimitedRange(arr3, n3, max_val3);

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

    return 0;
}