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.