Skip to main content

Count Sort Program

Counting sort is an efficient linear sorting algorithm that works by counting the occurrences of each element in an array, and then using that information to reconstruct a sorted sequence. The algorithm assumes that the input consists of integers within a specific range and works by creating a frequency array to count the number of occurrences of each element in the input array.

Once the frequency array is populated, the algorithm uses the frequency array to determine the position of each element in the output array. This is done by iterating through the input array, and for each element, placing it in the correct position in the output array based on its frequency in the input array.

The time complexity of counting sort is O(n+k), where n is the number of elements in the input array and k is the range of the input elements. Counting sort is therefore an efficient algorithm for sorting arrays with a small range of integers. However, its space complexity is O(k), which can be a disadvantage for very large ranges of integers.

Overall, counting sort is a simple and efficient sorting algorithm that is particularly useful for sorting arrays of integers with a small range of values.

Here given code implementation process.

//C Program
//Count sort program
#include <stdio.h>
#include <stdlib.h>
#define ALPHABET 256

void count_sort(char arr[],int size)
{
  
  //Create auxiliary space which is store information about character element
  int slot[ALPHABET];

  for (int i = 0; i < ALPHABET; ++i)
  {
    //Set each slot to zero
    slot[i]=0;
  }
  for (int i = 0; i < size; ++i)
  {
    //store the number of occurrences of character
    slot[(int)arr[i]]++;
  }
  for (int i = 0,j=0; i < ALPHABET && j<size; ++i)
  {
    //Assign value to actual array when slots are not empty
    while(slot[i] > 0)
    {
      arr[j] = (char) i;
      slot[i]--;
      j++;
    }
  }
}

int main()
{
 
 
  //Array of characters
  char arr[]= {'o','k','f','i','n','d','c','b','o','o','k','t','e','x','t','o','o','7','\0'};

  //Get the size of array
  int size=sizeof(arr)/sizeof(arr[0]);

  
  printf("Before Sort : %s\n",arr );

  count_sort(arr,size-1);

  printf("After Sort : %s\n",arr );

 
  return 0;
}

Output

Before Sort : okfindcbooktextoo7
After Sort : 7bcdefikknooooottx
#include<iostream>

using namespace std;

/*
  C++ Program
  Count Sort Program
*/
class MySort {
	public:
		int alphabet;
	MySort() {
		this->alphabet = 256;
	}
	void count_sort(char arr[], int size) {
		int slot[alphabet];
		for (int i = 0; i < this->alphabet; ++i) {
			//Set each slot to zero
			slot[i] = 0;
		}
		for (int i = 0; i < size; ++i) {
			//store the number of occurrences of character
			slot[(int) arr[i]]++;
		}
		for (int i = 0, j = 0; i < this->alphabet && j < size; ++i) {
			//Assign value to actual array when slots are not empty
			while (slot[i] > 0) {
				arr[j] = (char) i;
				slot[i]--;
				j++;
			}
		}
	}
	//Display array elements
	void print_array(char arr[], int size) {
		for (int i = 0; i < size; i++) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
};
int main() {
	MySort obj ;
	char arr[] = {
		'o',
		'k',
		'f',
		'i',
		'n',
		'd',
		'c',
		'b',
		'o',
		'o',
		'k',
		't',
		'e',
		'x',
		't',
		'o',
		'o',
		'7',
		'\0'
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "Before Sort :\n";
	obj.print_array(arr, size);
	obj.count_sort(arr, size-1);
	cout << "After Sort : \n";
	obj.print_array(arr, size);
	return 0;
}

Output

Before Sort :
 o k f i n d c b o o k t e x t o o 7
After Sort :
 7 b c d e f i k k n o o o o o t t x 
/*
  Java Program
  Count Sort Program
*/
public class MySort {

  public int alphabet;
  MySort()
  {
    alphabet=256;
  }

  public void count_sort(char []arr,int size)
  {
    
    //Create auxiliary space which is store information about character element
    int []slot= new int[alphabet];

    for (int i = 0; i < alphabet; ++i)
    {
      //Set each slot to zero
      slot[i]=0;
    }
    for (int i = 0; i < size; ++i)
    {
      //store the number of occurrences of character
      slot[(int)arr[i]]++;
    }
    for (int i = 0,j=0; i < alphabet && j<size; ++i)
    {
      //Assign value to actual array when slots are not empty
      while(slot[i] > 0)
      {
        arr[j] = (char)i;
        slot[i]--;
        j++;
      }
    }
  }
  //Display array elements
  public void print_array(char []arr,int size)
  {
    
    for(int i=0;i<size;i++)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }
  public static void main(String[] args) 
  {
  

    MySort obj = new MySort();
    //Array of characters
    char []arr= {'o','k','f','i','n','d','c','b','o','o','k','t','e','x','t','o','o','7'};


    //Get the size of array
    int size=arr.length;

    System.out.print("Before Sort :\n");
    obj.print_array(arr,size);
    obj.count_sort(arr,size);

    System.out.print("After Sort : \n");
    obj.print_array(arr,size);
  }
}

Output

Before Sort :
  o  k  f  i  n  d  c  b  o  o  k  t  e  x  t  o  o  7  
After Sort : 
  7  b  c  d  e  f  i  k  k  n  o  o  o  o  o  t  t  x  
using System;

/*
  C# Program
  Count Sort Program
*/

public class MySort {
	int alphabet;
	MySort() {
		alphabet = 256;
	}
	public void count_sort(char[] arr, int size) {
		
		//Create auxiliary space which is store information about character element
		int[] slot = new int[alphabet];
		for (int i = 0; i < alphabet; ++i) {
			//Set each slot to zero
			slot[i] = 0;
		}
		for (int i = 0; i < size; ++i) {
			//store the number of occurrences of character
			slot[(int) arr[i]]++;
		}
		for (int i = 0, j = 0; i < alphabet && j < size; ++i) {
			//Assign value to actual array when slots are not empty
			while (slot[i] > 0) {
				arr[j] = (char) i;
				slot[i]--;
				j++;
			}
		}
	}
	//Display array elements
	public void print_array(char[] arr, int size) {
		for (int i = 0; i < size; i++) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public static void Main(String[] args) {
		MySort obj = new MySort();
		char[]
		//Array of characters
		arr = {
			'o',
			'k',
			'f',
			'i',
			'n',
			'd',
			'c',
			'b',
			'o',
			'o',
			'k',
			't',
			'e',
			'x',
			't',
			'o',
			'o',
			'7'
			
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("Before Sort :\n");
		obj.print_array(arr, size);
		obj.count_sort(arr, size);
		Console.Write("After Sort : \n");
		obj.print_array(arr, size);
	}
}

Output

Before Sort :
 o k f i n d c b o o k t e x t o o 7
After Sort :
 7 b c d e f i k k n o o o o o t t x
<?php
/*
  Php Program
  Count Sort Program
*/
class MySort {
  public $alphabet;

  function __construct() {
    $this->alphabet = 256;
  }
  public  function count_sort(&$arr, $size) {
    //Create auxiliary space which is store information about character element
    $slot = array_fill(0, $this->alphabet, 0);
    for ($i = 0; $i < $this->alphabet; ++$i) {
      //Set each slot to zero
      $slot[$i] = 0;
    }
    for ($i = 0; $i < $size; ++$i) {
      //store the number of occurrences of character
      $location = ord($arr[$i]);
    
      $slot[$location]++;
    }

    for ($i = 0, $j = 0; $i < $this->alphabet && $j < $size; ++$i) {
      //Assign value to actual array when slots are not empty
      while ($slot[$i] > 0) {
      
        $arr[$j] = chr($i);
        $slot[$i]--;
        $j++;
      }
    }
  }
  //Display array elements

  public  function print_array($arr, $size) {
    for ($i = 0; $i < $size; $i++) {
      echo(" ". $arr[$i]);
    }
    echo("\n");
  }
};

function main() {

  $obj = new MySort();
  //Array of characters
  $arr = array('o', 'k', 'f', 'i', 'n', 'd', 'c', 'b', 'o', 'o', 'k', 't', 'e', 'x', 't', 'o', 'o', '7');
  //Get the size of array
  $size = count($arr);
  echo("Before Sort :\n");
  $obj->print_array($arr, $size);
  $obj->count_sort($arr, $size);
  echo("After Sort : \n");
  $obj->print_array($arr, $size);

}
main();

Output

Before Sort :
 o k f i n d c b o o k t e x t o o 7
After Sort :
 7 b c d e f i k k n o o o o o t t x
/*
  Node Js Program
  Count Sort Program
*/
class MySort {
	;
	constructor() {
		this.alphabet = 256;
	}
	count_sort(arr, size) {
		//Create auxiliary space which is store information about character element
		var slot = Array(this.alphabet).fill(0);
	

		for (var i = 0; i < size; ++i) {
			//store the number of occurrences of character
			slot[arr[i].charCodeAt()]++;
		}

		for (var i = 0,j = 0; i < this.alphabet && j < size; ++i) {
			//Assign value to actual array when slots are not empty
			while (slot[i] > 0) {
				arr[j] = String.fromCharCode(i);
				slot[i]--;
				j++;
			}
		}
	}

	//Display array elements
	print_array(arr, size) {
		for (var i = 0; i < size; i++) {
			process.stdout.write(" " + arr[i]);
		}

		process.stdout.write("\n");
	}
}

function main(args) {
	var obj = new MySort();
	//Array of characters
	var arr = ['o', 'k', 'f', 'i', 'n', 'd', 'c', 'b', 'o', 'o', 'k', 't', 'e', 'x', 't', 'o', 'o', '7'];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("Before Sort :\n");
	obj.print_array(arr, size);
	obj.count_sort(arr, size);
	process.stdout.write("After Sort : \n");
	obj.print_array(arr, size);
}

main();

Output

Before Sort :
 o k f i n d c b o o k t e x t o o 7
After Sort :
 7 b c d e f i k k n o o o o o t t x
#   Python 3 Program
#   Count Sort Program
class MySort :
	
	def __init__(self) :
		self.alphabet = 256
	
	def count_sort(self, arr, size) :
		slot = [0] * self.alphabet
		i = 0
		while (i < size) :
			# store the number of occurrences of character
			slot[ord(arr[i])] += 1
			i += 1
		
		i = 0
		j = 0
		while (i < self.alphabet and j < size) :
			# Assign value to actual array when slots are not empty
			while (slot[i] > 0) :
				arr[j] = chr(i)
				slot[i] -= 1
				j += 1
			
			i += 1
		
	
	# Display array elements
	def print_array(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MySort()
	arr = ['o', 'k', 'f', 'i', 'n', 'd', 'c', 'b', 'o', 'o', 'k', 't', 'e', 'x', 't', 'o', 'o', '7']
	size = len(arr)
	print("Before Sort :\n", end = "")
	obj.print_array(arr, size)
	obj.count_sort(arr, size)
	print("After Sort : \n", end = "")
	obj.print_array(arr, size)


if __name__ == "__main__":
	main()

Output

Before Sort :
  o  k  f  i  n  d  c  b  o  o  k  t  e  x  t  o  o  7
After Sort :
  7  b  c  d  e  f  i  k  k  n  o  o  o  o  o  t  t  x
#   Ruby Program
#   Count Sort Program
class MySort 
	# Define the accessor and reader of class MySort
	attr_reader :alphabet
	attr_accessor :alphabet
	def initialize() 
		@alphabet = 256
	end
	def count_sort(arr, size) 
		slot = Array.new(@alphabet, 0)
		i = 0
		while (i < size) 
			# store the number of occurrences of character
			slot[arr[i].ord] += 1
			i += 1
		end
		i = 0
		j = 0
		while (i < @alphabet && j < size) 
			# Assign value to actual array when slots are not empty
			while (slot[i] > 0) 
				arr[j] = i.chr
				slot[i] -= 1
				j += 1
			end
			i += 1
		end
	end
	# Display array elements
	def print_array(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
end
def main() 
	obj = MySort.new()
	arr = ['o', 'k', 'f', 'i', 'n', 'd', 'c', 'b', 'o', 'o', 'k', 't', 'e', 'x', 't', 'o', 'o', '7']
	size = arr.length
	print("Before Sort  :\n")
	obj.print_array(arr, size)
	obj.count_sort(arr, size)
	print("After Sort  :\n")
	obj.print_array(arr, size)
end


main()

Output

Before Sort  :
 o k f i n d c b o o k t e x t o o 7
After Sort  :
 7 b c d e f i k k n o o o o o t t x

/*
  Scala Program
  Count Sort Program
*/
class MySort (var alphabet: Int){
	

	def this() {
		this(256);
	}
	def count_sort(arr: Array[Char], size: Int): Unit = {
		var slot: Array[Int] = Array.fill[Int](this.alphabet)(0);
        var i: Int = 0;

        while (i < size) {
            //store the number of occurrences of character
            slot(arr(i).toInt) += 1;
            i += 1;
        }
        i = 0;
        var j: Int = 0;
        while (i < this.alphabet && j < size) {
            //Assign value to actual array when slots are not empty
            while (slot(i) > 0) {
                arr(j) = i.toChar;
                slot(i) -= 1;
                j += 1;
            }
            i += 1;
        }
    }
    //Display array elements
    def print_array(arr: Array[Char], size: Int): Unit = {
        var i: Int = 0;
        while (i < size) {
            print(" " + arr(i));
            i += 1;
        }
        print("\n");
    }
 }
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MySort = new MySort();
		val arr: Array[Char] = Array('o', 'k', 'f', 'i', 'n', 'd', 'c', 'b', 'o', 'o', 'k', 't', 'e', 'x', 't', 'o', 'o', '7');
		val size: Int = arr.length;
		print("Before Sort :\n");
		obj.print_array(arr, size);
		obj.count_sort(arr, size);
		print("After Sort : \n");
		obj.print_array(arr, size);
	}
}

Output

Before Sort :
 o k f i n d c b o o k t e x t o o 7
After Sort :
 7 b c d e f i k k n o o o o o t t x
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