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
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