Example: Sort Array by Frequency - Manual Count & Bubble Sort in C

// Sort Array by Frequency - Manual Count & Bubble Sort
#include <stdio.h>
#include <stdlib.h> // For INT_MIN (though not strictly necessary for this approach, good for general practice)

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

// 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
    // Max size of this array can be 'n' (if all elements are unique)
    struct ElementFreq freqArray[n];
    int uniqueCount = 0; // Tracks the number of unique elements found

    // Step 3: Count frequencies of each unique element
    // Mark elements as visited by setting them to a value like INT_MIN
    // This modifies the original array, so make a copy if needed.
    // For simplicity, we'll iterate and use a 'visited' flag logic or check for existing.
    // A better way is to iterate and then check if the element has already been added to freqArray.

    for (int i = 0; i < n; i++) {
        int isPresent = 0;
        // Check if current element arr[i] is already in freqArray
        for (int j = 0; j < uniqueCount; j++) {
            if (freqArray[j].value == arr[i]) {
                freqArray[j].frequency++;
                isPresent = 1;
                break;
            }
        }
        // If not present, add it as a new unique element
        if (!isPresent) {
            freqArray[uniqueCount].value = arr[i];
            freqArray[uniqueCount].frequency = 1;
            uniqueCount++;
        }
    }

    // Step 4: Sort the freqArray using Bubble Sort
    // Sort criteria:
    // 1. By frequency in descending order
    // 2. If frequencies are same, by value in ascending order
    for (int i = 0; i < uniqueCount - 1; i++) {
        for (int j = 0; j < uniqueCount - i - 1; j++) {
            // Compare frequencies
            if (freqArray[j].frequency < freqArray[j+1].frequency) {
                // Swap if current freq is less than next freq
                struct ElementFreq temp = freqArray[j];
                freqArray[j] = freqArray[j+1];
                freqArray[j+1] = temp;
            } else if (freqArray[j].frequency == freqArray[j+1].frequency) {
                // If frequencies are equal, compare values
                if (freqArray[j].value > freqArray[j+1].value) {
                    // Swap if current value is greater than next value
                    struct ElementFreq temp = freqArray[j];
                    freqArray[j] = freqArray[j+1];
                    freqArray[j+1] = temp;
                }
            }
        }
    }

    // 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;
}