Frequency Sort

Frequency sort reorders a collection based on the frequency or count of each unique element. Elements with higher frequencies appear earlier in the sorted output.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void frequencySort(int[] arr) {
  Map<Integer, Integer> freqMap = new HashMap<>();
  
  // Build frequency map
  for (int n: arr) {
    freqMap.put(n, freqMap.getOrDefault(n, 0) + 1); 
  }

  PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = 
      new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

  // Add frequencies to heap  
  maxHeap.addAll(freqMap.entrySet()); 

  // Sort by frequency descending
  List<Integer> sorted = new ArrayList<>();
  while (!maxHeap.isEmpty()) {
    Map.Entry<Integer, Integer> entry = maxHeap.poll();
    for (int i = 0; i < entry.getValue(); i++) {
      sorted.add(entry.getKey());
    }
  }

  // Load back into original array
  for (int i = 0; i < arr.length; i++) {
    arr[i] = sorted.get(i);
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void frequencySort(vector<int>& arr) {
  
  unordered_map<int, int> freqMap;

  for (int n : arr) {
    freqMap[n]++;
  }

  priority_queue<pair<int, int>> maxHeap;
  
  for (auto entry : freqMap) {
    maxHeap.push({entry.second, entry.first}); 
  }

  vector<int> sorted;
  while (!maxHeap.empty()) {
    int freq = maxHeap.top().first;
    int element = maxHeap.top().second;
    maxHeap.pop();

    for (int i = 0; i < freq; i++) {
      sorted.push_back(element);
    }
  }

  for (int i = 0; i < arr.size(); i++) {
    arr[i] = sorted[i];
  }
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from collections import Counter

def frequency_sort(arr):
  
  freq = Counter(arr)
  
  max_heap = []
  for element, frequency in freq.items():
    heapq.heappush(max_heap, (-frequency, element))
  
  sorted_arr = []
  while max_heap:
    frequency, element = heapq.heappop(max_heap)
    for _ in range(-frequency):
      sorted_arr.append(element)

  arr[:] = sorted_arr

Frequency sort is useful for gaining insights into data and biasing sorts based on occurrence count.

Frequency Sort is a method of sorting elements based on how often they appear in a given collection. In other words, elements are arranged in descending order by the frequency of their occurrences, so the element that appears most frequently will be placed first, followed by the element that appears the second most frequently, and so on. If two elements have the same frequency, their relative order might depend on the specific algorithm being used.

Solution

Java

In Java, you can use a HashMap to count the frequency of each element and then sort the keys based on their frequencies.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class FrequencySort {
    public static void main(String[] args) {
        int[] nums = {4, 2, 2, 8, 3, 3, 3};
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list, (a, b) -> map.get(b).compareTo(map.get(a)));

        int index = 0;
        for (int num : list) {
            int count = map.get(num);
            while (count-- > 0) {
                nums[index++] = num;
            }
        }

        System.out.println(Arrays.toString(nums)); // Output: [3, 3, 3, 2, 2, 4, 8]
    }
}

C++

In C++, you can use the STL map to store the frequency and then sort the elements using sort.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

bool compare(std::pair<int, int>& a, std::pair<int, int>& b) {
    return a.second > b.second;
}

int main() {
    std::vector<int> nums = {4, 2, 2, 8, 3, 3, 3};
    std::map<int, int> counts;
    for (int num : nums) {
        counts[num]++;
    }

    std::vector<std::pair<int, int>> pairs(counts.begin(), counts.end());
    std::sort(pairs.begin(), pairs.end(), compare);

    int index = 0;
    for (auto& pair : pairs) {
        int count = pair.second;
        while (count-- > 0) {
            nums[index++] = pair.first;
        }
    }

    for (int num : nums) {
        std::cout << num << " "; // Output: 3 3 3 2 2 4 8
    }

    return 0;
}

Python

In Python, you can use the collections.Counter class along with sorted to perform frequency sorting.

1
2
3
4
5
6
from collections import Counter

nums = [4, 2, 2, 8, 3, 3, 3]
counts = Counter(nums)
sorted_nums = sorted(nums, key=lambda x: (-counts[x], x))
print(sorted_nums)  # Output: [3, 3, 3, 2, 2, 4, 8]

Here, the Counter class is used to count the frequency of each element, and the sorted function is used to sort the elements by their frequencies in descending order. The lambda function in the key argument ensures that elements are sorted by frequency, and in case of ties, by their values.