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:
#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 code for the above approach
import 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
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 arr
arr = [2, 5, 2, 8, 5, 6, 8, 8]
sortedArr = sortByFrequency(arr)
print(sortedArr)
# by phasing17
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
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
Sort elements by frequency
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}