AlphaCodingSkills

Counting Sort


Advertisements

Previous Page Next Page

Counting sort is based on the idea that the number of occurrences of distinct elements is counted and stored in another array (say frequency array), by mapping the value of the distinct elements with index numbers of the array. The frequency array is then iterated over to use distinct elements and their occurrences and put them into the output array in a sorted way.

Example:

To understand the counting sort, lets consider an unsorted array $$A = [9, 1, 2, 5, 9, 9, 2, 1, 3, 3]$$ and discuss each step taken to sort the array in ascending order.

Step 1: In this step, the largest element of the $$A[ ]$$ is found out which is $$(9)$$ and an another array called $$frequency$$ is initiated with size $$[max(A[ ])+1$$]. Then the array $$A[ ]$$ is iterated over to store the number of occurrences of each distinct element in $$frequency$$ array, by mapping the distinct elements with index number of $$frequency$$ array.

Counting Sort

Step 2: In this step, the $$frequency$$ array is iterated over to get the information about each distinct element and its occurrences which is further used to build the sorted array.

Counting Sort

Counting sort is used most efficiently when the range of input elements is not significantly larger than the number of elements to be sorted. Along with this, the same concept can be used with negative input data as well.

Implementation of Counting Sort



# function for counting sort
def countingsort(MyList):
  n = len(MyList)
  max = 0
  #find largest element in the Array
  for i in MyList:
    if max < i:
      max = i

  #Create a freq array to store number of occurrences of 
  #each unique elements in the given list
  freq = [0 for i in range(0,max+1)] 
  for i in range(0,n):
    freq[MyList[i]] += 1

  #sort the given array using freq list
  j=0
  for i in range(0, max+1): 
    while freq[i]>0:
      MyList[j] = i
      j +=1
      freq[i] -= 1 

# function to print list
def PrintList(MyList):
  for i in MyList:
    print(i, end=" ")
  print("\n")
  
# test counting sort code                 
MyList = [9, 1, 2, 5, 9, 9, 2, 1, 3, 3]
print("Original List")
PrintList(MyList)

countingsort(MyList)
print("Sorted List")
PrintList(MyList)

Output

Original List
9 1 2 5 9 9 2 1 3 3 

Sorted List
1 1 2 2 3 3 5 9 9 9 



public class MyClass {
  // function for counting sort
  static void countingsort(int Array[]) {
   int n = Array.length;
   int max = 0;
   //find largest element in the Array
   for (int i=0; i<n; i++) 
   {  
     if(max < Array[i])
     {
       max = Array[i];
     } 
   }
   //Create a freq array to store number of occurrences of 
   //each unique elements in the given array 
   int[] freq = new int[max+1];
   for (int i=0; i<max+1; i++) 
   {  
     freq[i] = 0;
   } 
   for (int i=0; i<n; i++) 
   {  
     freq[Array[i]]++;
   }
   //sort the given array using freq array
   for (int i=0, j=0; i<=max; i++) 
   {  
     while(freq[i]>0)
     { 
       Array[j] = i;
       j++;
       freq[i]--;
     }
   }
  }

  // function to print array
  static void PrintArray(int Array[]) 
    { 
        int n = Array.length; 
        for (int i=0; i<n; i++) 
        {  
          System.out.print(Array[i] + " "); 
        }
        System.out.println(); 
    } 

  //test counting sort code
  public static void main(String[] args) {
    int[] MyArray =  {9, 1, 2, 5, 9, 9, 2, 1, 3, 3};
    System.out.println("Original Array");
    PrintArray(MyArray);

    countingsort(MyArray);
    System.out.println("\nSorted Array");
    PrintArray(MyArray);  
  }
}

Output

 
Original Array
9 1 2 5 9 9 2 1 3 3 

Sorted Array
1 1 2 2 3 3 5 9 9 9 



#include <iostream>
using namespace std;

  // function for counting sort
  static void countingsort(int Array[], int n) 
  {
    int max = 0;
    //find largest element in the Array
    for (int i=0; i<n; i++) 
      {  
        if(max < Array[i])
        {
           max = Array[i];
        } 
      }
    //Create a freq array to store number of occurrences of 
    //each unique elements in the given array 
    int freq[max+1];
    for (int i=0; i<max+1; i++) 
     {  
         freq[i] = 0;
     } 
    for (int i=0; i<n; i++) 
     {  
         freq[Array[i]]++;
     } 
     //sort the given array using freq array
     for (int i=0, j=0; i<=max; i++) 
      {  
        while(freq[i]>0)
        {
          Array[j] = i;
          j++;
          freq[i]--;
        }
      } 
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
      {  
        cout<<Array[i]<<" "; 
      }
    cout<<"\n"; 
  } 

 // test counting sort code
 int main (){
    int MyArray[] = {9, 1, 2, 5, 9, 9, 2, 1, 3, 3};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    cout<<"Original Array\n";
    PrintArray(MyArray, n);

    countingsort(MyArray, n);
    cout<<"\nSorted Array\n";
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
9 1 2 5 9 9 2 1 3 3 

Sorted Array
1 1 2 2 3 3 5 9 9 9 



#include <stdio.h>

  // function for counting sort
  static void countingsort(int Array[], int n) 
  {
    int max = 0;
    //find largest element in the Array
    for (int i=0; i<n; i++) 
      {  
        if(max < Array[i])
        {
           max = Array[i];
        } 
      }
    //Create a freq array to store number of occurrences of 
    //each unique elements in the given array 
    int freq[max+1] ;
    for (int i=0; i<max+1; i++) 
     {  
         freq[i] = 0;
     } 
    for (int i=0; i<n; i++) 
     {  
         freq[Array[i]]++;
     } 
     //sort the given array using freq array
     for (int i=0, j=0; i<=max; i++) 
      {  
        while(freq[i]>0)
        {
          Array[j] = i;
          j++;
          freq[i]--;
        }
      } 
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      printf("%i ",Array[i]); 
    }
    printf("\n"); 
  } 

 // test counting sort code
 int main (){
    int MyArray[] = {9, 1, 2, 5, 9, 9, 2, 1, 3, 3};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    printf("Original Array\n");
    PrintArray(MyArray, n);

    countingsort(MyArray, n);
    printf("\nSorted Array\n");
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
9 1 2 5 9 9 2 1 3 3 

Sorted Array
1 1 2 2 3 3 5 9 9 9 



using System;

namespace MyApplication { 
   class MyProgram {
     // function for counting sort
     static void countingsort(int[] Array) 
     {
      int n = Array.Length;
      int max = 0;
      //find largest element in the Array
      for (int i=0; i<n; i++) 
      {  
        if(max < Array[i])
        {
           max = Array[i];
        } 
      }
      //Create a freq array to store number of occurrences of 
      //each unique elements in the given array 
      int[] freq = new int[max+1];
      for (int i=0; i<max+1; i++) 
      {  
        freq[i] = 0;
      } 
      for (int i=0; i<n; i++) 
      {  
        freq[Array[i]]++;
      }
     //sort the given array using freq array
     for (int i=0, j=0; i<=max; i++) 
     {  
       while(freq[i]>0)
       { 
         Array[j] = i;
         j++;
         freq[i]--;
       }
     }
    }

     // function to print array
     static void PrintArray(int[] Array) 
     { 
        int n = Array.Length; 
        for (int i=0; i<n; i++) 
        {  
          Console.Write(Array[i] + " "); 
        }
        Console.Write("\n"); 
     } 
 
    // test counting sort code
    static void Main(string[] args) {
     int[] MyArray = {9, 1, 2, 5, 9, 9, 2, 1, 3, 3};
     Console.Write("Original Array\n");
     PrintArray(MyArray);

     countingsort(MyArray);
     Console.Write("\nSorted Array\n");
     PrintArray(MyArray);  
    }
  }
} 

Output

Original Array
9 1 2 5 9 9 2 1 3 3 

Sorted Array
1 1 2 2 3 3 5 9 9 9 

Time Complexity:

The time complexity to iterate over the input data is $$\mathcal{O}(N)$$, where $$N$$ is the number of elements in unsorted array and the time complexity to iterate over the $$frequency$$ array is $$\mathcal{O}(K)$$, where $$K$$ is the range of input data. The overall time complexity of counting sort is $$\mathcal{O}(N+K)$$ in all cases.


Previous Page Next Page