Skip to main content

Sort array elements by frequency

Sorting array by using element frequency

Here given code implementation process.

//C++ Program 
//Sort array elements by frequency
#include <iostream>
#include <map> 
#include <vector>


using namespace std;

void occurrence(int arr[],int size)
{

  map<int, int> mp; 

  map <int , vector<int> > result;

  map<int, int> :: iterator element;

  map<int, vector<int>> :: iterator output;
  
  vector<int> :: iterator it;

  int j = size-1;

  

  //Find the frequency of array elements
  for (int i = 0; i < size; ++i)
  { 
    mp[arr[i]]++;
  }

  for (element = mp.begin(); element != mp.end(); ++element)
  {
    result[element->second].insert(result[element->second].begin(),element->first);
  }

  for (output = result.begin(); output != result.end(); ++output)
  {
    
    for(it = result[output->first].begin();it != result[output->first].end(); it++)
    {
      for(int i=0; i < output->first && j>=0;i++,j--)
      {
        //store the new result into array
        arr[j]=*it;
      }

    }
  }
  
    
}
void print_data(int arr[],int size)
{
  for (int i = 0; i < size; ++i)
  {
    cout<<arr[i]<<"  " ;
  }
  cout<<endl;
}
int main()
{
    //Array element
    int arr[] = {1, 3, 7, 4, 7, 4, 3,7, 4, 8, 7};
    //Get the size of array
    int size = sizeof(arr)/sizeof(arr[0]);
    print_data(arr,size);
    occurrence(arr,size);
    print_data(arr,size);
    return 0;
}

Output

  1  3  7  4  7  4  3  7  4  8  7
  7  7  7  7  4  4  4  3  3  1  8

/*
Java program
Sort array elements by frequency
*/
import java.util.*; 
public class Hashing 
{ 
  public static void occurrence(int []arr)
  {
    Map<Integer, Integer> map = new HashMap<>();
    Map<Integer, List<Integer>> result   = new HashMap<>();
    int j = arr.length-1;
    for (int i=0;i<arr.length ; i++ ) 
    {
      if (map.containsKey(arr[i])) 
      {  
        //when key exist then put new key
        map.put(arr[i],map.get(arr[i])+1);
      }
      else
      {
        map.put(arr[i],1);
      }
    }
    for(int key : map.keySet())
    {
      if (result.containsKey(map.get(key))) 
      { 
        result.get(map.get(key)).add(0,key);
      }
      else
      {
        // map.get(current_sum).add(i);
        result.put(map.get(key), new ArrayList<Integer> ());
        result.get(map.get(key)).add(0,key);
      }
    }
    for (int key : result.keySet()) 
    {
      for(int value: result.get(key))
      {

        for (int i=0;i<key && j >=0 ;i++,j-- ) 
        {
          arr[j]=value;
        }
      }
    }

  }
  public static void  print_data(int []arr)
  {
    int size=arr.length;
    for (int i = 0; i < size; ++i)
    {
      System.out.print(arr[i]+"  ") ;
    }
    System.out.println();
  }
  public static void main(String[] args) 
  {
    //Array element
    int []arr = {1, 3, 7, 4, 7, 4, 3,7, 4, 8, 7};
    print_data(arr);
    occurrence(arr);
    print_data(arr);
  }
}

Output

1  3  7  4  7  4  3  7  4  8  7  
7  7  7  7  4  4  4  3  3  1  8 
#Python program
#Sort array elements by frequency

class Hashing:

  def occurrence(self,listData):

    frequency={}
    output={}

    for key in listData:

      if key in frequency:
        frequency[key] += 1
      else:
        frequency[key] = 1
    

    for key, value in frequency.items():
      
      if value in output:
        output[value].insert(0,key)
      else:
         output[value] = [key]
   
    j=len(listData)-1
   
    for key, value in output.items():

      for element in value:
        i=0 
        while i<key and j >=0 :
          listData[j]=element
          i+=1
          j-=1


def main():
  obj = Hashing()
  #define list element
  item =[1, 3, 7, 4, 7, 4, 3,7, 4, 8, 7]
  print(item)
  obj.occurrence(item)
  print(item)

if __name__=="__main__":
  main()

Output

[1, 3, 7, 4, 7, 4, 3, 7, 4, 8, 7]
[7, 7, 7, 7, 4, 4, 4, 3, 3, 8, 1]
/*
C# program
Sort array elements by frequency
*/
using System;
using System.Collections.Generic;
public class Hashing 
{ 
  public static void occurrence(int []arr)
  {
    SortedDictionary<int,int> map = new SortedDictionary<int,int>();
    SortedDictionary<int,List<int>> result = new SortedDictionary<int,List<int>>();
    int j = arr.Length - 1;
    for (int i=0;i<arr.Length ; i++ ) 
    {
      if (map.ContainsKey(arr[i])) 
      {  
        //when key exist then put new key
        map[arr[i]]=map[arr[i]]+1;
      }
      else
      {
        map.Add(arr[i],1);
      }
    }
    foreach(KeyValuePair<int, int> entry in map)
    {
      
      if (result.ContainsKey(entry.Value)) 
      {  
        //when value exist then add new element in list
        result[entry.Value].Insert(0,entry.Key);
      }
      else
      {
        result[entry.Value]=new List<int>(){entry.Key};
      }
    }

    foreach(KeyValuePair<int, List<int>> entry in result)
    {
      
      for (int i = 0; i < (entry.Value).Count;i++ ) 
      {
        for (int k = 0; k <entry.Key ; k++,j--) 
        {
          arr[j]=entry.Value[i];
        }
      }

    }

  }
  public static void  print_data(int []arr)
  {
    int size=arr.Length;
    for (int i = 0; i < size; ++i)
    {
      Console.Write(arr[i]+"  ") ;
    }
    Console.WriteLine();
  }
  public static void Main(String[] args) 
  {
    //Array element
    int []arr = {1, 3, 7, 4, 7, 4, 3,7, 4, 8, 7};
    print_data (arr);
    occurrence(arr);
    print_data (arr);
  }
}

Output

1  3  7  4  7  4  3  7  4  8  7  
7  7  7  7  4  4  4  3  3  1  8 
<?php 
/*
* PHP Program 
Sort array elements by frequency
*/


class Hashing
{

  public function occurrence(&$arr)
  {
    $size= count($arr);

    $frequency=array();
    $output=array();
    for ($i=0; $i < $size ; ++$i) 
    { 
      if(array_key_exists($arr[$i],$frequency))
      {
        $frequency[$arr[$i]]= $frequency[$arr[$i]]+1;
      }
      else
      {
        $frequency[$arr[$i]]=1;
      }
      
    }
    ksort($frequency);
    foreach ($frequency as $key => $value) 
    {
      if(array_key_exists($value,$output))
      {
        array_unshift($output[$value],$key);
      }
      else
      {
        $output[$value]=array($key);
      }
    }
    $j=$size-1;
    ksort($output);

    foreach ($output as $key => $value) 
    {
      foreach ($value as $location => $data) 
      {
        for ($i=0; $i <$key && $j>=0 ; $i++,$j--) 
        { 
          $arr[$j]=$data;
        }
      }
    }
  }
  public function  print_data( $arr)
  {
    $size= count($arr);
    for ( $i = 0; $i < $size; ++$i)
    {
      echo $arr[$i]."  " ;
    }
    echo "\n";
  }

}


function main()
{
 $obj =new Hashing();
 $arr=array(1, 3, 7, 4, 7, 4, 3,7, 4, 8, 7);
 $obj->print_data($arr);
 $obj->occurrence($arr);
 $obj->print_data($arr);
}
main();
?>

Output

1  3  7  4  7  4  3  7  4  8  7  
7  7  7  7  4  4  4  3  3  1  8
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