Print the elements of an array in the decreasing frequency if 2 numbers have the same frequency then print the one which came first
Examples:
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
Sort elements by frequency using sorting:
Follow the given steps to solve the problem:
- Use a sorting algorithm to sort the elements
- Iterate the sorted array and construct a 2D array of elements and count
- Sort the 2D array according to the count
Below is the illustration of the above approach:
Input: arr[] = {2 5 2 8 5 6 8 8}
Step1: Sort the array,
After sorting we get: 2 2 5 5 6 8 8 8Step 2: Now construct the 2D array to maintain the count of every element as
{{2, 2}, {5, 2}, { 6, 1}, {8, 3}}Step 3: Sort the array by count
{{8, 3}, {2, 2}, {5, 2}, {6, 1}}
How to maintain the order of elements if the frequency is the same?
The above approach doesn’t make sure the order of elements remains the same if the frequency is the same. To handle this, we should use indexes in step 3, if two counts are the same then we should first process(or print) the element with a lower index. In step 1, we should store the indexes instead of elements.
Input: arr[] = {2 5 2 8 5 6 8 8}
Step1: Sort the array,
After sorting we get: 2 2 5 5 6 8 8 8
indexes: 0 2 1 4 5 3 6 7
Step 2: Now construct the 2D array to maintain the count of every element as
Index, Count
0, 2
1, 2
5, 1
3, 3Step 3: Sort the array by count (consider indexes in case of tie)
{{3, 3}, {0, 2}, {1, 2}, {5, 1}}
Print the elements using indexes in the above 2D array
Below is the implementation of the above approach:
CPP
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Used for sortingstruct ele { int count, index, val;};// Used for sorting by valuebool mycomp(struct ele a, struct ele b){ return (a.val < b.val);}// Used for sorting by frequency. And if frequency is same,// then by appearancebool mycomp2(struct ele a, struct ele b){ if (a.count != b.count) return (a.count < b.count); else return a.index > b.index;}void sortByFrequency(int arr[], int n){ struct ele element[n]; for (int i = 0; i < n; i++) { // Fill Indexes element[i].index = i; // Initialize counts as 0 element[i].count = 0; // Fill values in structure // elements element[i].val = arr[i]; } /* Sort the structure elements according to value, we used stable sort so relative order is maintained. */ stable_sort(element, element + n, mycomp); /* initialize count of first element as 1 */ element[0].count = 1; /* Count occurrences of remaining elements */ for (int i = 1; i < n; i++) { if (element[i].val == element[i - 1].val) { element[i].count += element[i - 1].count + 1; /* Set count of previous element as -1, we are doing this because we'll again sort on the basis of counts (if counts are equal than on the basis of index)*/ element[i - 1].count = -1; /* Retain the first index (Remember first index is always present in the first duplicate we used stable sort. */ element[i].index = element[i - 1].index; } /* Else If previous element is not equal to current so set the count to 1 */ else element[i].count = 1; } /* Now we have counts and first index for each element so now sort on the basis of count and in case of tie use index to sort.*/ stable_sort(element, element + n, mycomp2); for (int i = n - 1, index = 0; i >= 0; i--) if (element[i].count != -1) for (int j = 0; j < element[i].count; j++) arr[index++] = element[i].val;}// Driver codeint main(){ int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call sortByFrequency(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0;} |
Java
// Java program to sort elements by frequency. If two// elements have same count, then put the elements that// appears first Importing required classesimport java.util.*;class ele { int count, index, val;}// Used for sorting by valueclass mycomp implements Comparator<ele> { public int compare(ele a, ele b) { return (a.val - b.val); }}// Used for sorting by frequency. And if frequency is same,// then by appearanceclass mycomp2 implements Comparator<ele> { public int compare(ele a, ele b) { if (a.count != b.count) return (a.count - b.count); return (b.index - a.index); }}class GFG { static void sortByFrequency(int[] arr, int n) { ArrayList<ele> element = new ArrayList<ele>(); // ele[] element = new ele[n]; for (int i = 0; i < n; i++) { element.add(new ele()); // Fill Indexes element.get(i).index = i; // Initialize counts as 0 element.get(i).count = 0; // Fill values in structure // elements element.get(i).val = arr[i]; } /* Sort the structure elements according to value, we used stable sort so relative order is maintained. */ Collections.sort(element, new mycomp()); /* initialize count of first element as 1 */ element.get(0).count = 1; /* Count occurrences of remaining elements */ for (int i = 1; i < n; i++) { if (element.get(i).val == element.get(i - 1).val) { element.get(i).count += element.get(i - 1).count + 1; /* Set count of previous element as -1, we are doing this because we'll again sort on the basis of counts (if counts are equal than on the basis of index)*/ element.get(i - 1).count = -1; /* Retain the first index (Remember first index is always present in the first duplicate we used stable sort. */ element.get(i).index = element.get(i - 1).index; } /* Else If previous element is not equal to current so set the count to 1 */ else element.get(i).count = 1; } /* Now we have counts and first index for each element so now sort on the basis of count and in case of tie use index to sort.*/ Collections.sort(element, new mycomp2()); for (int i = n - 1, index = 0; i >= 0; i--){ if (element.get(i).count != -1) { for (int j = 0; j < element.get(i).count;j++) arr[index++] = element.get(i).val; } } } // Driver code public static void main(String[] args) { int[] arr = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; int n = arr.length; // Function call sortByFrequency(arr, n); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }}// This code is contributed by Abhijeet Kumar(abhijeet19403) |
Python3
# Python3 program that performs the following# operations: Sort elements by frequency. If two elements# have same count, then put the elements that appears first# Used for sortingclass ele: def __init__(self): self.count = 0 self.index = 0 self.val = 0def mycomp(a): return a.val# Used for sorting by frequency. And if frequency is same,# then by appearancedef mycomp2(a): # using negative value for a.index # since the sorting should be in # descending order return (a.count, -a.index)def sortByFrequency(arr, n): element = [None for _ in range(n)] for i in range(n): element[i] = ele() # Fill Indexes element[i].index = i # Initialize counts as 0 element[i].count = 0 # Fill values in structure # elements element[i].val = arr[i] # Sort the structure elements according to value, # we used stable sort so relative order is maintained. # element.sort(key=mycomp) # initialize count of first element as 1 element[0].count = 1 # Count occurrences of remaining elements for i in range(1, n): if (element[i].val == element[i - 1].val): element[i].count += element[i - 1].count + 1 # Set count of previous element as -1, we are # doing this because we'll again sort on the # basis of counts (if counts are equal than on # the basis of index)*/ element[i - 1].count = -1 # Retain the first index (Remember first index # is always present in the first duplicate we # used stable sort. */ element[i].index = element[i - 1].index # Else If previous element is not equal to current # so set the count to 1 else: element[i].count = 1 # Now we have counts and first index for each element # so now sort on the basis of count and in case of tie # use index to sort.*/ element.sort(key=mycomp2) index = 0 for i in range(n - 1, -1, -1): if (element[i].count != -1): for j in range(element[i].count): arr[index] = element[i].val index += 1# Driver codearr = [2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8]n = len(arr)# Function callsortByFrequency(arr, n)print(*arr)# This code is contributed by phasing17 |
C#
// Sort elements by frequency. If two elements have same// count, then put the elements that appears firstusing System;using System.Collections.Generic;// Used for sortingclass ele { public int count, index, val;};// Used for sorting by valueclass mycomp : Comparer<ele> { public override int Compare(ele a, ele b) { return (a.val.CompareTo(b.val)); }};// Used for sorting by frequency. And if frequency is same,// then by appearanceclass mycomp2 : Comparer<ele> { public override int Compare(ele a, ele b) { if (a.count != b.count) return (a.count).CompareTo(b.count); return (b.index).CompareTo(a.index); }};class GFG { static void sortByFrequency(int[] arr, int n) { ele[] element = new ele[n]; for (int i = 0; i < n; i++) { element[i] = new ele(); // Fill Indexes element[i].index = i; // Initialize counts as 0 element[i].count = 0; // Fill values in structure // elements element[i].val = arr[i]; } /* Sort the structure elements according to value, we used stable sort so relative order is maintained. */ Array.Sort(element, new mycomp()); /* initialize count of first element as 1 */ element[0].count = 1; /* Count occurrences of remaining elements */ for (int i = 1; i < n; i++) { if (element[i].val == element[i - 1].val) { element[i].count += element[i - 1].count + 1; /* Set count of previous element as -1, we are doing this because we'll again sort on the basis of counts (if counts are equal than on the basis of index)*/ element[i - 1].count = -1; /* Retain the first index (Remember first index is always present in the first duplicate we used stable sort. */ element[i].index = element[i - 1].index; } /* Else If previous element is not equal to current so set the count to 1 */ else element[i].count = 1; } /* Now we have counts and first index for each element so now sort on the basis of count and in case of tie use index to sort.*/ Array.Sort(element, new mycomp2()); for (int i = n - 1, index = 0; i >= 0; i--) if (element[i].count != -1) for (int j = 0; j < element[i].count; j++) arr[index++] = element[i].val; } // Driver code public static void Main(string[] args) { int[] arr = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; int n = arr.Length; // Function call sortByFrequency(arr, n); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program that performs the following// operations: Sort elements by frequency. If two elements// have same count, then put the elements that appears first// Used for sortingclass ele{ constructor() { this.count = 0 this.index = 0 this.val = 0 }}function mycomp(a, b){ return a.val - b.val}// Used for sorting by frequency. And if frequency is same,// then by appearancefunction mycomp2(a, b){ // using negative value for a.index // since the sorting should be in // descending order if (a.count == b.count) return b.index - a.index return a.count - b.count}function sortByFrequency(arr, n){ let element = new Array(n) for (var i = 0; i < n; i++) { element[i] = new ele() // Fill Indexes element[i].index = i // Initialize counts as 0 element[i].count = 0 // Fill values in structure // elements element[i].val = arr[i] } // Sort the structure elements according to value, // we used stable sort so relative order is maintained. // element.sort(mycomp) // initialize count of first element as 1 element[0].count = 1 // Count occurrences of remaining elements for (var i = 1; i < n; i++) { if (element[i].val == element[i - 1].val) { element[i].count += element[i - 1].count + 1 // Set count of previous element as -1, we are // doing this because we'll again sort on the // basis of counts (if counts are equal than on // the basis of index)*/ element[i - 1].count = -1 // Retain the first index (Remember first index // is always present in the first duplicate we // used stable sort. */ element[i].index = element[i - 1].index } // Else If previous element is not equal to current // so set the count to 1 else element[i].count = 1 } // Now we have counts and first index for each element // so now sort on the basis of count and in case of tie // use index to sort.*/ element.sort(mycomp2) let index = 0 for (var i = n - 1; i >= 0; i--) if (element[i].count != -1) for (var j = 0; j < element[i].count; j++) { arr[index] = element[i].val index += 1 }}// Driver codelet arr = [2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8]let n = arr.length// Function callsortByFrequency(arr, n)console.log(arr.join(" "))// This code is contributed by phasing17 |
Output
8 8 8 2 2 5 5 6 -1 9999999
Time Complexity: O(N log N), where the N is the size of the array
Auxiliary Space: O(N)
Thanks to Gaurav Ahirwar for providing the above implementation
Sort elements by frequency using hashing and sorting:
To solve the problem follow the below idea:
Using a hashing mechanism, we can store the elements (also the first index) and their counts in a hash. Finally, sort the hash elements according to their counts
Below is the implementation of the above approach:
CPP
// CPP program for above approach#include <bits/stdc++.h>using namespace std;// Compare functionbool fcompare(pair<int, pair<int, int> > p, pair<int, pair<int, int> > p1){ if (p.second.second != p1.second.second) return (p.second.second > p1.second.second); else return (p.second.first < p1.second.first);}void sortByFrequency(int arr[], int n){ unordered_map<int, pair<int, int> > hash; // hash map for (int i = 0; i < n; i++) { if (hash.find(arr[i]) != hash.end()) hash[arr[i]].second++; else hash[arr[i]] = make_pair(i, 1); } // store the count of all the elements in the hashmap // Iterator to Traverse the Hashmap auto it = hash.begin(); // Vector to store the Final Sortted order vector<pair<int, pair<int, int> > > b; for (it; it != hash.end(); ++it) b.push_back(make_pair(it->first, it->second)); sort(b.begin(), b.end(), fcompare); // Printing the Sorted sequence for (int i = 0; i < b.size(); i++) { int count = b[i].second.second; while (count--) cout << b[i].first << " "; }}// Driver codeint main(){ int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call sortByFrequency(arr, n); return 0;} |
Java
// Java program for above approachimport java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.List;class GFG { static Integer[] arr = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; // Driver Code public static void main(String[] args) { List<Integer> list = Arrays.asList(arr); // Function call sortBasedOnFrequencyAndValue(list); } // Compare Function public static void sortBasedOnFrequencyAndValue(List<Integer> list) { int n = arr.length; final HashMap<Integer, Integer> mapCount = new HashMap<Integer, Integer>(); final HashMap<Integer, Integer> mapIndex = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { if (mapCount.containsKey(arr[i])) { mapCount.put(arr[i], mapCount.get(arr[i]) + 1); } else { mapCount.put( arr[i], 1); // Map to capture Count of elements mapIndex.put(arr[i], i); // Map to capture 1st // occurrence of elements } } Collections.sort(list, new Comparator<Integer>() { public int compare(Integer n1, Integer n2) { int freq1 = mapCount.get(n1); int freq2 = mapCount.get(n2); if (freq1 != freq2) { return freq2 - freq1; } else { return mapIndex.get(n1) - mapIndex.get( n2); // Elements with Lesser // Index gets Higher // Priority } } }); System.out.println(list); }} |
Python3
# Python3 program for above approachfrom collections import defaultdict# Sort by Frequencydef sortByFreq(arr, n): # arr -> Array to be sorted # n -> Length of Array # d is a hashmap(referred as dictionary in python) d = defaultdict(lambda: 0) for i in range(n): d[arr[i]] += 1 # Sorting the array 'arr' where key # is the function based on which # the array is sorted # While sorting we want to give # first priority to Frequency # Then to value of item arr.sort(key=lambda x: (-d[x], x), reverse = True) #require Updation:- reverse = True, to sort an array in descending order (Jayesh Verma) return (arr)# Driver codeif __name__ == "__main__": arr = [2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8] n = len(arr) # Function call solution = sortByFreq(arr, n) print(*solution) |
C#
// C# program to implement the approachusing System;using System.Collections.Generic;public class GFG { static int[] arr; // Compare Function public static void sortBasedOnFrequencyAndValue(List<int> list) { int n = arr.Length; Dictionary<int, int> mapCount = new Dictionary<int, int>(); Dictionary<int, int> mapIndex = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (mapCount.ContainsKey(arr[i])) { mapCount[arr[i]]++; } else { mapCount[arr[i]] = 1; // Map to capture Count of elements mapIndex[arr[i]] = i; // Map to capture 1st occurrence of // elements } } list.Sort( (int n1, int n2) => mapCount[n1] != mapCount[n2] ? mapCount[n2].CompareTo(mapCount[n1]) : mapIndex[n1].CompareTo(mapIndex[n2]) // Elements with Lesser // Index gets Higher // Priority ); foreach(var i in list) Console.Write(i + " "); } // Driver Code public static void Main(string[] args) { arr = new int[] { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 }; List<int> list = new List<int>(arr); // Function call sortBasedOnFrequencyAndValue(list); }}// This code is contributed by phasing17 |
Javascript
<script>let arr=[2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8];// Compare Functionfunction sortBasedOnFrequencyAndValue(list){ let n = arr.length; let mapCount = new Map(); let mapIndex = new Map(); for (let i = 0; i < n; i++) { if (mapCount.has(arr[i])) { mapCount.set(arr[i], mapCount.get(arr[i]) + 1); } else { mapCount.set(arr[i],1); // Map to capture Count of elements mapIndex.set(arr[i],i); // Map to capture 1st occurrence of elements } } list.sort(function(n1,n2){ let freq1 = mapCount.get(n1); let freq2 = mapCount.get(n2); if (freq1 != freq2) { return freq2 - freq1; } else { return mapIndex.get(n1) - mapIndex.get( n2); // Elements with Lesser // Index gets Higher // Priority } }); document.write(list.join(" "));}// Driver CodesortBasedOnFrequencyAndValue(arr);// This code is contributed by patel2127</script> |
Output
8 8 8 2 2 5 5 6 -1 9999999
Time Complexity: O(N log N), where the N is the size of the array
Auxiliary Space: O(N)
Note: This can also be solved by Using two maps, one for array element as an index and after this second map whose keys are frequency and value are array elements.
Sort elements by frequency using BST:
Follow the given steps to solve the problem:
- Insert elements in BST one by one and if an element is already present then increment the count of the node. The node of the Binary Search Tree (used in this approach) will be as follows.
C++
class tree { public: int element; int first_index; /*To handle ties in counts*/ int count;}tree BST; |
C
struct tree { int element; int first_index /*To handle ties in counts*/ int count;} BST; |
Java
static class tree { int element; int first_index; /*To handle ties in counts*/ int count;}tree BST = new tree();// This code is contributed by gauravrajput1 |
Python3
# Python code to implement the approachclass Tree: element = None # to handle ties first_index = None count = NoneBST = Tree()# This code is contributed by phasing17 |
C#
public class tree { public int element; public int first_index; /* To handle ties in counts */ public int count;}tree BST = new tree();// This code is contributed by gauravrajput1 |
Javascript
// JS code to implement the approachclass tree { constructor() { this.element; this.first_index; //To handle ties in counts this.count; } };// This code is contributed by phasing17 |
- Store the first indexes and corresponding counts of BST in a 2D array.
- Sort the 2D array according to counts (and use indexes in case of a tie).
Implementation of the this approach: Set 2
Time Complexity: O(N log N) if a Self Balancing Binary Search Tree is used.
Auxiliary Space: O(N)
Sort elements by frequency using Heap:
Follow the given steps to solve the problem:
- Take the arr and use unordered_map to have VALUE : FREQUENCY Table
- Then make a HEAP such that high frequency remains at TOP and when frequency is same, just keep in ascending order (Smaller at TOP)
- Then After full insertion into Heap
- Pop one by one and copy it into the Array
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ppi pair<int, int>/*IMPORTANT: comparator works in prority_queue only if theyare a class which hasoperator() overloaded in it (got this from stackoverflow) */class Compare {public: bool operator()(pair<int, int> a, pair<int, int> b) { // b is at top and a is at bottom - have that in // mind if (a.first == b.first) // when freq same return a.second > b.second; // smaller val stays at top return a.first < b.first; // higher freq stays at top }};void solve(vector<int>& arr){ int N = arr.size(); unordered_map<int, int> mpp; // val, freq for (int a : arr) { mpp[a]++; } // max heap - as max wise freq elements is what needed priority_queue<ppi, vector<ppi>, Compare> maxH; for (auto m : mpp) { maxH.push({ m.second, m.first }); // freq, val } // now the max freq is at TOP of MAX heap int i = 0; // to maintain index to copy while (maxH.size() > 0) { int val = maxH.top().second; // val int freq = maxH.top().first; // freq while (freq--) { // freq - those many times make a copy arr[i] = val; i++; } maxH.pop(); // heapify happens and next top freq ele // goes up }}// Driver codeint main(){ vector<int> vec{ 2, 5, 2, 8, 5, 6, 8, 8 }; int n = vec.size(); // Function call solve(vec); for (int i = 0; i < n; i++) cout << vec[i] << " "; cout << "\n"; return 0;}// Code done by Balakrishnan R (rbkraj000) |
Java
import java.util.*;class Compare implements Comparator<Map.Entry<Integer, Integer> > { public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) { // b is at top and a is at bottom - have that in // mind if (a.getValue() == b.getValue()) // when freq same return a.getKey().compareTo( b.getKey()); // smaller val stays at top return b.getValue().compareTo( a.getValue()); // higher freq stays at top }}class Main { static void solve(List<Integer> arr) { int N = arr.size(); Map<Integer, Integer> mpp = new HashMap<>(); // val, freq for (int a : arr) { mpp.put(a, mpp.getOrDefault(a, 0) + 1); } // max heap - as max wise freq elements is what // needed PriorityQueue<Map.Entry<Integer, Integer> > maxH = new PriorityQueue<>(new Compare()); for (Map.Entry<Integer, Integer> m : mpp.entrySet()) { maxH.add(m); // freq, val } // now the max freq is at TOP of MAX heap int i = 0; // to maintain index to copy while (maxH.size() > 0) { int val = maxH.peek().getKey(); // val int freq = maxH.peek().getValue(); // freq while (freq-- > 0) { // freq - those many times make a copy arr.set(i, val); i++; } maxH.poll(); // heapify happens and next top // freq ele goes up } } public static void main(String[] args) { List<Integer> arr = Arrays.asList(2, 5, 2, 8, 5, 6, 8, 8); int n = arr.size(); // Function call solve(arr); for (int i = 0; i < n; i++) System.out.print(arr.get(i) + " "); System.out.println(); }}// This code is contributed by divyansh2212 |
Python3
from collections import defaultdictfrom queue import PriorityQueueclass Compare: def __init__(self, freq, val): self.freq = freq self.val = val def __lt__(self, other): if self.freq == other.freq: return self.val < other.val return self.freq > other.freqdef solve(arr): n = len(arr) mpp = defaultdict(int) for a in arr: mpp[a] += 1 max_heap = PriorityQueue() for key, value in mpp.items(): max_heap.put(Compare(value, key)) i = 0 while not max_heap.empty(): item = max_heap.get() freq = item.freq val = item.val for _ in range(freq): arr[i] = val i += 1 return arrvec = [2, 5, 2, 8, 5, 6, 8, 8]print(solve(vec)) |
C#
using System;using System.Collections.Generic;using System.Linq;class KVCompare : IComparer<KeyValuePair<int, int> > { public int Compare(KeyValuePair<int, int> a, KeyValuePair<int, int> b) { // b is at top and a is at bottom - have that in // mind if (a.Value == b.Value) // when freq same return a.Key.CompareTo( b.Key); // smaller val stays at top return b.Value.CompareTo( a.Value); // higher freq stays at top }}class GFG { static void Solve(List<int> arr) { int n = arr.Count; Dictionary<int, int> mpp = new Dictionary<int, int>(); // val, freq foreach(int a in arr) { if (mpp.ContainsKey(a)) mpp[a]++; else mpp[a] = 1; } // sorted list - as max wise freq elements is what // needed SortedList<KeyValuePair<int, int>, bool> maxH = new SortedList<KeyValuePair<int, int>, bool>( new KVCompare()); foreach(KeyValuePair<int, int> m in mpp) { maxH.Add(m, true); // freq, val } // now the max freq is at TOP of MAX heap int i = 0; // to maintain index to copy while (maxH.Count > 0) { int val = maxH.Keys[0].Key; // val int freq = maxH.Keys[0].Value; // freq while (freq-- > 0) { // freq - those many times make a copy arr[i] = val; i++; } maxH.RemoveAt( 0); // heapify happens and next top // freq ele goes up } } public static void Main(string[] args) { List<int> arr = new List<int>() { 2, 5, 2, 8, 5, 6, 8, 8 }; int n = arr.Count; // Function call Solve(arr); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); Console.WriteLine(); }}// This code is contributed by phasing17 |
Javascript
// Define the `solve` functionfunction solve(arr) { // Find the length of the array let N = arr.length; // Create an empty map to store the frequency of each element in the array let mpp = {}; // Loop through the array to count the frequency of each element for (let i = 0; i < N; i++) { if (mpp[arr[i]] === undefined) { // If the element has not been encountered before, add it to the map with a frequency of 1 mpp[arr[i]] = 1; } else { // If the element has been encountered before, increment its frequency by 1 mpp[arr[i]]++; } } // Create an empty array to store the frequency and value of each element let maxH = []; // Loop through the map to add the frequency and value of each element to the `maxH` array for (let key in mpp) { maxH.push([mpp[key], key]); } // Sort the `maxH` array in descending order of frequency, and ascending order of value if frequency is equal maxH.sort((a, b) => { if (a[0] === b[0]) { return b[1] - a[1]; } return a[0] - b[0]; }); // Initialize a variable `i` to 0 let i = 0; // Loop through the sorted `maxH` array while (maxH.length > 0) { // Get the frequency and value of the current element let freq = maxH[maxH.length - 1][0]; let val = maxH[maxH.length - 1][1]; // Fill the `arr` with the value `freq` times, starting from the `i`-th index for (let j = 0; j < freq; j++) { arr[i] = val; i++; } // Remove the current element from the `maxH` array maxH.pop(); }}// Test the function with an example arraylet vec = [2, 5, 2, 8, 5, 6, 8, 8];solve(vec);console.log(vec);// This code is contributed by Nayan Nand |
Output
8 8 8 2 2 5 5 6
The code and approach is done by Balakrishnan R.
Time Complexity: O(d * log(d)) (Dominating factor O(n + 2 * d * log (d))). O(n) (unordered map insertion- as 1 insertion takes O(1)) + O(d*log(d)) (Heap insertion – as one insertion is log N complexity) + O(d*log(d)) (Heap Deletion – as one pop takes Log N complexity)
Here d = No. of Distinct Elements, n = Total no. of elements (size of input array). (Always d<=n depends on the array)
Auxiliary Space: O(d), As heap and map is used
Sort elements by frequency using Quicksort:
Follow the given steps to solve the problem:
- Make a structure called “ele” with two fields called “val” and “count” to hold the value and count of each element in the input array.
- Make an array of “ele” structures of size n, where n is the size of the input array, and set the “val” field of each element to the value from the input array and the “count” field to 0.
- Traverse through the input array and for each element, increase the count field of the corresponding “ele” structure by 1.
- Using the quicksort method and a custom comparison function for elements, sort the “ele” array in decreasing order of count and rising order of value.
- Finally, recreate the input array by iterating over the sorted “ele” array in descending order of count and adding the value of each element to the input array count number of times equal to its count field.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;struct ele { int val, count;};void swap(struct ele* a, struct ele* b){ struct ele temp = *a; *a = *b; *b = temp;}int partition(struct ele arr[], int low, int high){ struct ele pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j].count < pivot.count || (arr[j].count == pivot.count && arr[j].val > pivot.val)) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1);}void quicksort(struct ele arr[], int low, int high){ if (low < high) { int pi = partition(arr, low, high); quicksort(arr, low, pi - 1); quicksort(arr, pi + 1, high); }}void sortByFrequency(int arr[], int n){ struct ele element[n]; for (int i = 0; i < n; i++) { element[i].val = arr[i]; element[i].count = 0; } for (int i = 0; i < n; i++) { int j; for (j = 0; j < i; j++) if (arr[i] == arr[j]) break; if (i == j) element[i].count++; else element[j].count++; } quicksort(element, 0, n - 1); for (int i = n - 1, index = 0; i >= 0; i--) { for (int j = 0; j < element[i].count; j++) arr[index++] = element[i].val; }}int main(){ int arr[] = { 2, 5, 2, 8, 5, 6, 8, 8}; int n = sizeof(arr) / sizeof(arr[0]); sortByFrequency(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0;}// This code is contributed by Vaibhav Saroj |
Java
// Java code for the above approachimport java.util.Arrays;public class GFG { static class ele { public int val; public int count; } static void swap(ele[] arr, int i, int j) { ele temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static int partition(ele[] arr, int low, int high) { ele pivot = arr[high]; int i = low - 1; for (int j = low; j <= high - 1; j++) { if (arr[j].count < pivot.count || (arr[j].count == pivot.count && arr[j].val > pivot.val)) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } static void quicksort(ele[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quicksort(arr, low, pi - 1); quicksort(arr, pi + 1, high); } } static void sortByFrequency(int[] arr, int n) { ele[] element = new ele[n]; for (int i = 0; i < n; i++) { element[i] = new ele(); element[i].val = arr[i]; element[i].count = 0; } for (int i = 0; i < n; i++) { int j; for (j = 0; j < i; j++) if (arr[i] == arr[j]) break; if (i == j) element[i].count++; else element[j].count++; } quicksort(element, 0, n - 1); for (int i = n - 1, index = 0; i >= 0; i--) { for (int j = 0; j < element[i].count; j++) arr[index++] = element[i].val; } } public static void main(String[] args) { int[] arr = { 2, 5, 2, 8, 5, 6, 8, 8 }; int n = arr.length; sortByFrequency(arr, n); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }}// This code is contributed by Pushpesh Raj |
Python
def sortByFrequency(arr): element = [] for i in range(len(arr)): element.append({'val': arr[i], 'count': 0}) for i in range(len(arr)): j = 0 while j < i: if arr[i] == arr[j]: break j += 1 if i == j: element[i]['count'] += 1 else: element[j]['count'] += 1 def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j]['count'] < pivot['count'] or (arr[j]['count'] == pivot['count'] and arr[j]['val'] > pivot['val']): i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quicksort(arr, low, high): if low < high: pi = partition(arr, low, high) quicksort(arr, low, pi - 1) quicksort(arr, pi + 1, high) quicksort(element, 0, len(arr) - 1) index = 0 for i in range(len(arr) - 1, -1, -1): for j in range(element[i]['count']): arr[index] = element[i]['val'] index += 1 return arrarr = [2, 5, 2, 8, 5, 6, 8, 8]sortedArr = sortByFrequency(arr)print(sortedArr)# by phasing17 |
C#
using System;public class Program{ struct ele { public int val; public int count; } static void swap(ref ele a, ref ele b) { ele temp = a; a = b; b = temp; } static int partition(ele[] arr, int low, int high) { ele pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; j++) { if (arr[j].count < pivot.count || (arr[j].count == pivot.count && arr[j].val > pivot.val)) { i++; swap(ref arr[i], ref arr[j]); } } swap(ref arr[i + 1], ref arr[high]); return (i + 1); } static void quicksort(ele[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quicksort(arr, low, pi - 1); quicksort(arr, pi + 1, high); } } static void sortByFrequency(int[] arr, int n) { ele[] element = new ele[n]; for (int i = 0; i < n; i++) { element[i].val = arr[i]; element[i].count = 0; } for (int i = 0; i < n; i++) { int j; for (j = 0; j < i; j++) if (arr[i] == arr[j]) break; if (i == j) element[i].count++; else element[j].count++; } quicksort(element, 0, n - 1); for (int i = n - 1, index = 0; i >= 0; i--) { for (int j = 0; j < element[i].count; j++) arr[index++] = element[i].val; } } static void Main() { int[] arr = { 2, 5, 2, 8, 5, 6, 8, 8 }; int n = arr.Length; sortByFrequency(arr, n); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); }}// This code is contributed by Vaibhav Saroj |
Javascript
function sortByFrequency(arr) { const element = []; for (let i = 0; i < arr.length; i++) { element[i] = { val: arr[i], count: 0 }; } for (let i = 0; i < arr.length; i++) { let j; for (j = 0; j < i; j++) { if (arr[i] == arr[j]) { break; } } if (i == j) { element[i].count++; } else { element[j].count++; } } function swap(a, b) { const temp = a; a = b; b = temp; } function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j <= high - 1; j++) { if ( arr[j].count < pivot.count || (arr[j].count == pivot.count && arr[j].val > pivot.val) ) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } function quicksort(arr, low, high) { if (low < high) { const pi = partition(arr, low, high); quicksort(arr, low, pi - 1); quicksort(arr, pi + 1, high); } } quicksort(element, 0, arr.length - 1); for (let i = arr.length - 1, index = 0; i >= 0; i--) { for (let j = 0; j < element[i].count; j++) { arr[index++] = element[i].val; } } return arr;}const arr = [2, 5, 2, 8, 5, 6, 8, 8];const sortedArr = sortByFrequency(arr);console.log(sortedArr);// This code is contributed by Vaibhav Saroj |
Output
8 8 8 2 2 5 5 6
This Quicksort approach and code is contributed by Vaibhav Saroj.
Time complexity: O(n log n).
Space complexity: O(n).
Related Article: Sort elements by frequency | Set 2
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
