Sort elements by frequency
The problem being addressed is to sort elements in an array based on their frequency. This task involves arranging the elements in such a way that elements with higher frequency appear earlier in the array, and in case of equal frequencies, the elements should be sorted in ascending order. This operation is useful in various scenarios, such as analyzing data with repeated values or optimizing certain algorithms.
Problem Statement and Description
Given an array of integers, the goal is to sort the elements based on their frequency. If two elements have the same
frequency, they should be sorted in ascending order. For example, consider the array
[6, 5, 4, 1, 6, 5, 5, 2, 9, 3, 1, 2, 2, 2]
. After sorting by frequency, the output could be
[2, 2, 2, 2, 5, 5, 5, 6, 6, 1, 1, 4, 9, 3]
.
Idea to Solve the Problem
To sort the elements by frequency, we can first create a frequency record for each unique element. Then, using this record, we can rearrange the original array by placing elements in order of decreasing frequency.
Pseudocode
difference(arr, value, index):
if value > arr[index]:
return value - arr[index]
else:
return arr[index] - value
arrange(arr, size, index, counter):
if index < 0:
return
data = arr[index]
arrange(arr, size, index - 1, counter)
for i from *counter to size-1:
if arr[i] == data:
swap arr[i] and arr[*counter]
increment *counter
sort_by_frequency(arr, size):
sets = 1
for i from 0 to size-2:
if arr[i] != arr[i+1]:
increment sets
if sets > 1:
record[sets][2]
counter = 0
for i from 0 to size-2:
increment length
if arr[i] != arr[i+1]:
record[counter][0] = arr[i]
record[counter][1] = length
reset length
increment counter
if record[counter-1][0] != arr[size-1]:
record[counter][0] = arr[size-1]
record[counter][1] = 1
length = 0
for i from 0 to sets-1:
counter = i
for j from 0 to sets-1:
if record[counter][1] < record[j][1]:
counter = j
for k from 0 to record[counter][1]-1:
arr[length] = record[counter][0]
increment length
set record[counter][1] to -1
print_array(arr, size):
for i from 0 to size-1:
print arr[i]
sort_array(arr, size):
counter = 1
print_array(arr, size)
arrange(arr, size, size-1, &counter)
sort_by_frequency(arr, size)
print_array(arr, size)
Algorithm Explanation
- Create a function
difference(arr, value, index)
that calculates the difference between the givenvalue
and the element atarr[index]
. It returns the absolute difference. - Create a function
arrange(arr, size, index, counter)
that rearranges the array elements based on frequency. It uses a recursive approach to process each element and swap them based on the counter value. - Create a function
sort_by_frequency(arr, size)
that sorts the array based on frequency. It calculates the frequency record and uses it to rearrange the original array. - Create a function
print_array(arr, size)
that prints the elements of the array. - Create a function
sort_array(arr, size)
that initializes the counter, prints the array, arranges it based on frequency, and prints the sorted array.
Code Solution
//C Program
//Sort elements by frequency
#include <stdio.h>
//Combine array elements by occurrence sequence
void arrange(int arr[],int size,int index,int *counter)
{
if(index<0) return;
int data=arr[index];
arrange(arr,size,index-1,counter);
for (int i = *counter; i < size && *counter<size ; ++i)
{
if(arr[i]==data )
{
//swap element value
arr[i]=arr[*counter];
arr[*counter]=data;
(*counter)=*counter+1;
}
}
}
void sort_by_frequency(int arr[],int size)
{
int sets=1,length=0;
for (int i = 0; i < size-1; ++i)
{
//Get the unique element
if(arr[i] != arr[i+1])
{
sets++;
}
}
//Check that unique elements are more than one or not
if(sets > 1)
{
//Create a new memory to store frequency of element
int record[sets][2];
int counter = 0;
for (int i = 0; i < size-1; ++i)
{
length++;
if(arr[i] != arr[i+1])
{
//Assign value of array
record[counter][0] = arr[i];
//Assign value of element frequency
record[counter][1] = length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
counter++;
}
}
if(record[counter-1][0] != arr[size-1])
{
//Get the frequency of last element
record[counter][0]=arr[size-1];
record[counter][1]=1;
}
length=0;
for (int i = 0; i < sets; ++i)
{
counter = i;
for (int j = 0; j < sets; ++j)
{
if(record[counter][1]<record[j][1])
{
counter=j;
}
}
//Update actual array
for (int k = 0; k < record[counter][1]; ++k,++length)
{
arr[length]=record[counter][0];
}
//set frequency is -1
record[counter][1]=-1;
}
printf("\n");
}
}
//print array elements
void print_array(int arr[],int size)
{
printf("\n");
for(int i=0;i<size;i++)
{
printf("%3d",arr[i] );
}
}
void sort_array(int arr[],int size)
{
int counter=1;
print_array(arr,size);
arrange(arr,size,size-1,&counter);
sort_by_frequency(arr,size);
print_array(arr,size);
}
int main()
{
//define array elements
int arr[] = {6, 5, 4, 1, 6, 5, 5, 2, 9, 3, 1, 2, 2, 2 };
//Get the size of array
int size=(sizeof(arr)/sizeof(arr[0]));
sort_array(arr,size);
return 0;
}
Output
6 5 4 1 6 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 4 9 3
#include<iostream>
using namespace std;
/*
C++ Program
Sort elements by frequency
*/
class MyNumber {
public:
int counter;
MyNumber() {
this->counter = 0;
}
//Combine array elements by occurrence sequence
void arrange(int arr[], int size, int index) {
if (index < 0) {
return;
}
int data = arr[index];
this->arrange(arr, size, index - 1);
for (int i = this->counter; i < size && this->counter < size; ++i) {
if (arr[i] == data) {
//swap element value
arr[i] = arr[this->counter];
arr[this->counter] = data;
this->counter = this->counter + 1;
}
}
}
void sort_by_frequency(int arr[], int size) {
int sets = 1, length = 0;
for (int i = 0; i < size - 1; ++i) {
//Get the unique element
if (arr[i] != arr[i + 1]) {
sets++;
}
}
//Check that unique elements are more than one or not
if (sets > 1) {
//Create a new memory to store frequency of element
int record[sets][2];
int location = 0;
for (int i = 0; i < size - 1; ++i) {
length++;
if (arr[i] != arr[i + 1]) {
//Assign value of array
record[location][0] = arr[i];
//Assign value of element frequency
record[location][1] = length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
location++;
}
}
if (record[location - 1][0] != arr[size - 1]) {
//Get the frequency of last element
record[location][0] = arr[size - 1];
record[location][1] = 1;
}
length = 0;
for (int i = 0; i < sets; ++i) {
location = i;
for (int j = 0; j < sets; ++j) {
if (record[location][1] < record[j][1]) {
location = j;
}
}
//Update actual array
for (int k = 0; k < record[location][1]; ++k, ++length) {
arr[length] = record[location][0];
}
//set frequency is -1
record[location][1] = -1;
}
cout << "\n";
}
}
//print array elements
void print_array(int arr[], int size) {
cout << "\n";
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
void sort_array(int arr[], int size) {
this->counter = 1;
this->print_array(arr, size);
this->arrange(arr, size, size - 1);
this->sort_by_frequency(arr, size);
this->print_array(arr, size);
}
};
int main() {
MyNumber obj ;
int arr[] ={6, 5, 4, 1, 6, 5, 5, 2, 9, 3, 1, 2, 2, 2 };
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.sort_array(arr, size);
return 0;
}
Output
6 5 4 1 6 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 4 9 3
/*
Java Program
Sort elements by frequency
*/
public class MyNumber {
public int counter;
public MyNumber()
{
counter=0;
}
//Combine array elements by occurrence sequence
public void arrange(int []arr,int size,int index)
{
if(index < 0) {
return;
}
int data = arr[index];
arrange(arr,size,index-1);
for (int i = counter; i < size && counter < size ; ++i)
{
if(arr[i]==data )
{
//swap element value
arr[i] = arr[counter];
arr[counter] = data;
counter = counter+1;
}
}
}
public void sort_by_frequency(int []arr,int size)
{
int sets=1,length=0;
for (int i = 0; i < size-1; ++i)
{
//Get the unique element
if(arr[i] != arr[i+1])
{
sets++;
}
}
//Check that unique elements are more than one or not
if(sets > 1)
{
//Create a new memory to store frequency of element
int [][]record = new int[sets][2];
int location = 0;
for (int i = 0; i < size-1; ++i)
{
length++;
if(arr[i] != arr[i+1])
{
//Assign value of array
record[location][0] = arr[i];
//Assign value of element frequency
record[location][1] = length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
location++;
}
}
if(record[location-1][0] != arr[size-1])
{
//Get the frequency of last element
record[location][0]=arr[size-1];
record[location][1]=1;
}
length=0;
for (int i = 0; i < sets; ++i)
{
location = i;
for (int j = 0; j < sets; ++j)
{
if(record[location][1]<record[j][1])
{
location=j;
}
}
//Update actual array
for (int k = 0; k < record[location][1]; ++k,++length)
{
arr[length]=record[location][0];
}
//set frequency is -1
record[location][1]=-1;
}
System.out.print("\n");
}
}
//print array elements
public void print_array(int []arr,int size)
{
System.out.print("\n");
for(int i=0;i<size;i++)
{
System.out.print(" "+arr[i] );
}
}
public void sort_array(int []arr,int size)
{
counter=1;
print_array(arr,size);
arrange(arr,size,size-1);
sort_by_frequency(arr,size);
print_array(arr,size);
}
public static void main(String[] args) {
MyNumber obj = new MyNumber();
int []arr = { 6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2 };
//Get the size of array
int size = arr.length;
obj.sort_array(arr,size);
}
}
Output
6 5 4 1 6 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 4 9 3
/*
C# Program
Sort elements by frequency
*/
using System;
public class MyNumber {
public int counter;
public MyNumber() {
counter = 0;
}
//Combine array elements by occurrence sequence
public void arrange(int[] arr, int size, int index) {
if (index < 0) {
return;
}
int data = arr[index];
arrange(arr, size, index - 1);
for (int i = counter; i < size && counter < size; ++i) {
if (arr[i] == data) {
//swap element value
arr[i] = arr[counter];
arr[counter] = data;
counter = counter + 1;
}
}
}
public void sort_by_frequency(int[] arr, int size) {
int sets = 1,length = 0;
for (int i = 0; i < size - 1; ++i) {
//Get the unique element
if (arr[i] != arr[i + 1]) {
sets++;
}
}
//Check that unique elements are more than one or not
if (sets > 1) {
//Create a new memory to store frequency of element
int[,] record = new int[sets,2];
int location = 0;
for (int i = 0; i < size - 1; ++i) {
length++;
if (arr[i] != arr[i + 1]) {
//Assign value of array
record[location,0] = arr[i];
//Assign value of element frequency
record[location,1] =length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
location++;
}
}
if (record[location - 1,0] != arr[size - 1]) {
//Get the frequency of last element
record[location,0] = arr[size - 1];
record[location,1] = 1;
}
length = 0;
for (int i = 0; i < sets; ++i) {
location = i;
for (int j = 0; j < sets; ++j) {
if (record[location,1] < record[j,1]) {
location = j;
}
}
//Update actual array
for (int k = 0; k < record[location,1]; ++k, ++length) {
arr[length] = record[location,0];
}
//set frequency is -1
record[location,1] = -1;
}
Console.Write("\n");
}
}
//print array elements
public void print_array(int[] arr, int size) {
Console.Write("\n");
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
public void sort_array(int[] arr, int size) {
counter = 1;
print_array(arr, size);
arrange(arr, size, size - 1);
sort_by_frequency(arr, size);
print_array(arr, size);
}
public static void Main(String[] args) {
MyNumber obj = new MyNumber();
int []arr = {
6,
5,
4,
1,
6,
3,
5,
5,
2,
9,
3,
1,
2,
2,
2
};
//Get the size of array
int size = arr.Length;
obj.sort_array(arr, size);
}
}
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
# Python 3 Program
# Sort elements by frequency
class MyNumber :
def __init__(self) :
self.counter = 0
# Combine array elements by occurrence sequence
def arrange(self, arr, size, index) :
if (index < 0) :
return
data = arr[index]
self.arrange(arr, size, index - 1)
i = self.counter
while (i < size and self.counter < size) :
if (arr[i] == data) :
# swap element value
arr[i] = arr[self.counter]
arr[self.counter] = data
self.counter = self.counter + 1
i += 1
def sort_by_frequency(self, arr, size) :
sets = 1
length = 0
i = 0
j = 0
k = 0
while (i < size - 1) :
# Get the unique element
if (arr[i] != arr[i + 1]) :
sets += 1
i += 1
# Check that unique elements are more than one or not
if (sets > 1) :
record = [ [0] * 2 for _ in range(sets)]
location = 0
i = 0
while (i < size - 1) :
length += 1
if (arr[i] != arr[i + 1]) :
# Assign value of array
record[location][0] = arr[i]
# Assign value of element frequency
record[location][1] = length
# Reset the value of new element frequency is to zero
length = 0
# modified index of record array
location += 1
i += 1
if (record[location - 1][0] != arr[size - 1]) :
# Get the frequency of last element
record[location][0] = arr[size - 1]
record[location][1] = 1
length = 0
i = 0
while (i < sets) :
location = i
j = 0
while (j < sets) :
if (record[location][1] < record[j][1]) :
location = j
j += 1
# Update actual array
k = 0
while (k < record[location][1]) :
arr[length] = record[location][0]
k += 1
length += 1
# set frequency is -1
record[location][1] = -1
i += 1
print("\n")
# print array elements
def print_array(self, arr, size) :
print(end="\n")
i = 0
while (i < size) :
print(" ", arr[i],end="")
i += 1
def sort_array(self, arr, size) :
self.counter = 1
self.print_array(arr, size)
self.arrange(arr, size, size - 1)
self.sort_by_frequency(arr, size)
self.print_array(arr, size)
def main() :
obj = MyNumber()
arr = [6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2]
size = len(arr)
obj.sort_array(arr, size)
if __name__ == "__main__":
main()
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
# Ruby Program
# Sort elements by frequency
class MyNumber
# Define the accessor and reader of class MyNumber
attr_reader :counter
attr_accessor :counter
def initialize()
@counter = 0
end
# Combine array elements by occurrence sequence
def arrange(arr, size, index)
if (index < 0)
return
end
data = arr[index]
self.arrange(arr, size, index - 1)
i = @counter
while (i < size and @counter < size)
if (arr[i] == data)
# swap element value
arr[i] = arr[@counter]
arr[@counter] = data
@counter = @counter + 1
end
i += 1
end
end
def sort_by_frequency(arr, size)
sets = 1
length = 0
i = 0
j = 0
k = 0
while (i < size - 1)
# Get the unique element
if (arr[i] != arr[i + 1])
sets += 1
end
i += 1
end
# Check that unique elements are more than one or not
if (sets > 1)
record = Array.new(sets){Array.new(2,0)}
location = 0
i = 0
while (i < size - 1)
length += 1
if (arr[i] != arr[i + 1])
# Assign value of array
record[location][0] = arr[i]
# Assign value of element frequency
record[location][1] = length
# Reset the value of new element frequency is to zero
length = 0
# modified index of record array
location += 1
end
i += 1
end
if (record[location - 1][0] != arr[size - 1])
# Get the frequency of last element
record[location][0] = arr[size - 1]
record[location][1] = 1
end
length = 0
i = 0
while (i < sets)
location = i
j = 0
while (j < sets)
if (record[location][1] < record[j][1])
location = j
end
j += 1
end
# Update actual array
k = 0
while (k < record[location][1])
arr[length] = record[location][0]
k += 1
length += 1
end
# set frequency is -1
record[location][1] = -1
i += 1
end
print("\n")
end
end
# print array elements
def print_array(arr, size)
print("\n")
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
def sort_array(arr, size)
@counter = 1
self.print_array(arr, size)
self.arrange(arr, size, size - 1)
self.sort_by_frequency(arr, size)
self.print_array(arr, size)
end
end
def main()
obj = MyNumber.new()
arr = [6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2]
size = arr.length
obj.sort_array(arr, size)
end
main()
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
/*
Scala Program
Sort elements by frequency
*/
class MyNumber (var counter: Int){
def this() {
this(0);
}
//Combine array elements by occurrence sequence
def arrange(arr: Array[Int], size: Int, index: Int): Unit = {
if (index < 0) {
return;
}
var data: Int = arr(index);
this.arrange(arr, size, index - 1);
var i: Int = this.counter;
while (i < size && this.counter < size) {
if (arr(i) == data) {
//swap element value
arr(i) = arr(this.counter);
arr(this.counter) = data;
this.counter = this.counter + 1;
}
i += 1;
}
}
def sort_by_frequency(arr: Array[Int], size: Int): Unit = {
var sets: Int = 1;
var length: Int = 0;
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
while (i < size - 1) {
//Get the unique element
if (arr(i) != arr(i + 1)) {
sets += 1;
}
i += 1;
}
//Check that unique elements are more than one or not
if (sets > 1) {
var record: Array[Array[Int]] = Array.fill[Int](sets,2)(0);
var location: Int = 0;
i = 0;
while (i < size - 1) {
length += 1;
if (arr(i) != arr(i + 1)) {
//Assign value of array
record(location)(0) = arr(i);
//Assign value of element frequency
record(location)(1) = length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
location += 1;
}
i += 1;
}
if (record(location - 1)(0) != arr(size - 1)) {
//Get the frequency of last element
record(location)(0) = arr(size - 1);
record(location)(1) = 1;
}
length = 0;
i = 0;
while (i < sets) {
location = i;
j = 0;
while (j < sets) {
if (record(location)(1) < record(j)(1)) {
location = j;
}
j += 1;
}
//Update actual array
k = 0;
while (k < record(location)(1)) {
arr(length) = record(location)(0);
k += 1;
length += 1;
}
//set frequency is -1
record(location)(1) = -1;
i += 1;
}
print("\n");
}
}
//print array elements
def print_array(arr: Array[Int], size: Int): Unit = {
print("\n");
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
def sort_array(arr: Array[Int], size: Int): Unit = {
this.counter = 1;
this.print_array(arr, size);
this.arrange(arr, size, size - 1);
this.sort_by_frequency(arr, size);
this.print_array(arr, size);
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyNumber = new MyNumber();
var arr: Array[Int] = Array(6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2);
var size: Int = arr.length;obj.sort_array(arr, size);
}
}
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
/*
Swift 4 Program
Sort elements by frequency
*/
class MyNumber {
var counter : Int;
init() {
self.counter = 0;
}
//Combine array elements by occurrence sequence
func arrange(_ arr: inout [Int], _ size: Int, _ index: Int) {
if (index < 0) {
return;
}
let data: Int = arr[index];
self.arrange(&arr, size, index - 1);
var i: Int = self.counter;
while (i < size && self.counter < size) {
if (arr[i] == data) {
//swap element value
arr[i] = arr[self.counter];
arr[self.counter] = data;
self.counter = self.counter + 1;
}
i += 1;
}
}
func sort_by_frequency(_ arr: inout [Int], _ size: Int) {
var sets: Int = 1;
var length: Int = 0;
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
while (i < size - 1) {
//Get the unique element
if (arr[i] != arr[i + 1]) {
sets += 1;
}
i += 1;
}
//Check that unique elements are more than one or not
if (sets > 1) {
var record: [[Int]] = Array( repeating : Array( repeating:0 , count:2) , count:sets);
var location: Int = 0;
i = 0;
while (i < size - 1) {
length += 1;
if (arr[i] != arr[i + 1]) {
//Assign value of array
record[location][0] = arr[i];
//Assign value of element frequency
record[location][1] = length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
location += 1;
}
i += 1;
}
if (record[location - 1][0] != arr[size - 1]) {
//Get the frequency of last element
record[location][0] = arr[size - 1];
record[location][1] = 1;
}
length = 0;
i = 0;
while (i < sets) {
location = i;
j = 0;
while (j < sets) {
if (record[location][1] < record[j][1]) {
location = j;
}
j += 1;
}
//Update actual array
k = 0;
while (k < record[location][1]) {
arr[length] = record[location][0];
k += 1;
length += 1;
}
//set frequency is -1
record[location][1] = -1;
i += 1;
}
print(terminator:"\n");
}
}
//print array elements
func print_array(_ arr: [Int], _ size: Int) {
print(terminator:"\n");
var i: Int = 0;
while (i < size) {
print(" ", arr[i],terminator:"");
i += 1;
}
}
func sort_array(_ arr: inout [Int], _ size: Int) {
self.counter = 1;
self.print_array(arr, size);
self.arrange(&arr, size, size - 1);
self.sort_by_frequency(&arr, size);
self.print_array(arr, size);
}
}
func main() {
let obj: MyNumber = MyNumber();
var arr: [Int] = [6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2];
let size: Int = arr.count;
obj.sort_array(&arr, size);
}
main();
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
/*
Node Js Program
Sort elements by frequency
*/
class MyNumber {
constructor() {
this.counter = 0;
}
//Combine array elements by occurrence sequence
arrange(arr, size, index) {
if (index < 0) {
return;
}
var data = arr[index];
this.arrange(arr, size, index - 1);
for (var i = this.counter; i < size && this.counter < size; ++i) {
if (arr[i] == data) {
//swap element value
arr[i] = arr[this.counter];
arr[this.counter] = data;
this.counter = this.counter + 1;
}
}
}
sort_by_frequency(arr, size) {
var sets = 1;
var length = 0;
for (var i = 0; i < size - 1; ++i) {
//Get the unique element
if (arr[i] != arr[i + 1]) {
sets++;
}
}
//Check that unique elements are more than one or not
if (sets > 1) {
//Create a new memory to store frequency of element
var record = Array(sets).fill(0).map(() => new Array(2).fill(0));;
var location = 0;
for (var i = 0; i < size - 1; ++i) {
length++;
if (arr[i] != arr[i + 1]) {
//Assign value of array
record[location][0] = arr[i];
//Assign value of element frequency
record[location][1] = length;
//Reset the value of new element frequency is to zero
length = 0;
//modified index of record array
location++;
}
}
if (record[location - 1][0] != arr[size - 1]) {
//Get the frequency of last element
record[location][0] = arr[size - 1];
record[location][1] = 1;
}
length = 0;
for (var i = 0; i < sets; ++i) {
location = i;
for (var j = 0; j < sets; ++j) {
if (record[location][1] < record[j][1]) {
location = j;
}
}
//Update actual array
for (var k = 0; k < record[location][1]; ++k,
++length) {
arr[length] = record[location][0];
}
//set frequency is -1
record[location][1] = -1;
}
process.stdout.write("\n");
}
}
//print array elements
print_array(arr, size) {
process.stdout.write("\n");
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
sort_array(arr, size) {
this.counter = 1;
this.print_array(arr, size);
this.arrange(arr, size, size - 1);
this.sort_by_frequency(arr, size);
this.print_array(arr, size);
}
}
function main(args) {
var obj = new MyNumber();
var arr = [6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2];
//Get the size of array
var size = arr.length;
obj.sort_array(arr, size);
}
main();
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
<?php
/*
Php Program
Sort elements by frequency
*/
class MyNumber {
public $counter;
function __construct() {
$this->counter = 0;
}
//Combine array elements by occurrence sequence
public function arrange(&$arr, $size, $index) {
if ($index < 0) {
return;
}
$data = $arr[$index];
$this->arrange($arr, $size, $index - 1);
for ($i = $this->counter; $i < $size && $this->counter < $size; ++$i) {
if ($arr[$i] == $data) {
//swap element value
$arr[$i] = $arr[$this->counter];
$arr[$this->counter] = $data;
$this->counter = $this->counter + 1;
}
}
}
public function sort_by_frequency(&$arr, $size) {
$sets = 1;
$length = 0;
for ($i = 0; $i < $size - 1; ++$i) {
//Get the unique element
if ($arr[$i] != $arr[$i + 1]) {
$sets++;
}
}
//Check that unique elements are more than one or not
if ($sets > 1) {
//Create a new memory to store frequency of element
$record = array_fill(0, $sets, array_fill(0, 2, 0));
$location = 0;
for ($i = 0; $i < $size - 1; ++$i) {
$length++;
if ($arr[$i] != $arr[$i + 1]) {
//Assign value of array
$record[$location][0] = $arr[$i];
//Assign value of element frequency
$record[$location][1] = $length;
//Reset the value of new element frequency is to zero
$length = 0;
//modified index of record array
$location++;
}
}
if ($record[$location - 1][0] != $arr[$size - 1]) {
//Get the frequency of last element
$record[$location][0] = $arr[$size - 1];
$record[$location][1] = 1;
}
$length = 0;
for ($i = 0; $i < $sets; ++$i) {
$location = $i;
for ($j = 0; $j < $sets; ++$j) {
if ($record[$location][1] < $record[$j][1]) {
$location = $j;
}
}
//Update actual array
for ($k = 0; $k < $record[$location][1]; ++$k,++$length) {
$arr[$length] = $record[$location][0];
}
//set frequency is -1
$record[$location][1] = -1;
}
echo("\n");
}
}
//print array elements
public function print_array($arr, $size) {
echo("\n");
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
}
public function sort_array(&$arr, $size) {
$this->counter = 1;
$this->print_array($arr, $size);
$this->arrange($arr, $size, $size - 1);
$this->sort_by_frequency($arr, $size);
$this->print_array($arr, $size);
}
};
function main() {
$obj = new MyNumber();
$arr = array(6, 5, 4, 1, 6, 3, 5, 5, 2, 9, 3, 1, 2, 2, 2);
//Get the size of array
$size = count($arr);
$obj->sort_array($arr, $size);
}
main();
Output
6 5 4 1 6 3 5 5 2 9 3 1 2 2 2
2 2 2 2 5 5 5 6 6 1 1 3 3 4 9
Time Complexity Analysis
The algorithm calculates the frequency record and sorts the array based on frequency. Calculating the frequency record requires iterating through the array once. Sorting by frequency involves another iteration through the frequency record array, which is typically much smaller than the original array. The time complexity of this algorithm is O(n + m), where n is the size of the input array and m is the number of unique elements.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment