Frequency Sort – Numbers

Sort integers by their frequency in descending order, with ties broken by ascending value

Understand the Problem

Problem Statement

Given N integers, sort them based on their frequency in descending order. If the frequency is the same, sort based on their values in ascending order.

Constraints

1 <= N <= 10000
Each integer is within standard 32-bit signed integer range
Input contains exactly N integers on the second line

Examples

Example 1

Input

8
2 1 2 8 7 3 7 2

Output

2 2 2 7 7 1 3 8

Explanation

Number 2 appears 3 times (highest frequency), numbers 7 appears 2 times, and numbers 1, 3, 8 each appear once. Among the numbers with frequency 1, they are sorted in ascending order: 1, 3, 8.

Example 2

Input

5
5 4 3 2 1

Output

1 2 3 4 5

Explanation

All numbers appear exactly once (same frequency), so they are sorted by their values in ascending order.

Solution

#include <stdio.h>
#include <stdlib.h>

// Structure to hold number and its frequency
typedef struct {
    int value;
    int frequency;
} NumberFreq;

// Custom comparator for sorting
int compare(const void *a, const void *b) {
    NumberFreq *numA = (NumberFreq *)a;
    NumberFreq *numB = (NumberFreq *)b;
    
    // First sort by frequency (descending)
    if (numA->frequency != numB->frequency) {
        return numB->frequency - numA->frequency;
    }
    
    // If frequencies are equal, sort by value (ascending)
    return numA->value - numB->value;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[10000];
    int freqMap[200001] = {0}; // Assuming range -100000 to 100000
    int offset = 100000;
    
    // Read input and count frequencies
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        freqMap[arr[i] + offset]++;
    }
    
    // Create array of unique numbers with their frequencies
    NumberFreq numbers[10000];
    int uniqueCount = 0;
    
    for (int i = 0; i < n; i++) {
        int value = arr[i];
        int freq = freqMap[value + offset];
        
        // Check if this number is already in our list
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (numbers[j].value == value) {
                found = 1;
                break;
            }
        }
        
        if (!found) {
            numbers[uniqueCount].value = value;
            numbers[uniqueCount].frequency = freq;
            uniqueCount++;
        }
    }
    
    // Sort by frequency (descending) and value (ascending)
    qsort(numbers, uniqueCount, sizeof(NumberFreq), compare);
    
    // Print result
    for (int i = 0; i < uniqueCount; i++) {
        for (int j = 0; j < numbers[i].frequency; j++) {
            printf("%d ", numbers[i].value);
        }
    }
    
    return 0;
}

Time:O(n log n) - due to sorting the unique elements

Space:O(n) - for frequency map and structure array

Approach:

Step-by-step explanation:

Input Reading: Read N and the array of integers
Frequency Counting: Use an array-based hash map with offset to count frequencies of each number
Unique Numbers Collection: Create a structure array containing unique numbers and their frequencies
Custom Sorting: Use qsort with a comparator that sorts by frequency (descending) first, then by value (ascending)
Output Generation: Print each number repeated according to its frequency

The offset technique handles negative numbers by shifting the range to positive indices.

Visual Explanation

Loading diagram...

All Problems