Skip to main content

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

  1. Create a function difference(arr, value, index) that calculates the difference between the given value and the element at arr[index]. It returns the absolute difference.
  2. 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.
  3. 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.
  4. Create a function print_array(arr, size) that prints the elements of the array.
  5. 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.

Last updated on by Kalkicode




Comment

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