Counting Sort

In this sort, we count the frequencies of distinct elements of array and store them in an auxiliary array, by mapping its value as index of auxiliary array and then place each element in its proper position in the output array .

Complexity: As the above code runs in linear time so the complexity in worst case will be O(max + n), where n is the number of elements and max is the range of input element of array A[ ].

import java.util.Scanner;

class Count

{

void sort(int a[])

{

int max=a[0];

for(int i=1;i<a.length;i++)

{

if(a[i]>max)

max=a[i];

}

int count[]=new int[max+1];

int output[]=new int[a.length];

for(int i=0;i<a.length;i++)

count[a[i]]++;

for(int i=1;i<count.length;i++)

count[i]=count[i]+count[i-1];

for(int i=0;i<a.length;i++)

{

output[count[a[i]]-1]=a[i];

count[a[i]]=count[a[i]]-1;

}

System.out.println("the sorted array is:");

for(int i=0;i<output.length;i++)

System.out.println(output[i]+"\t");

}

}

class CountTest

{

public static void main(String args[])

{

Count c1=new Count();

System.out.println("enter the total number of elements:");

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int arr[]=new int[n];

for(int i=0;i<n;i++)

{

System.out.printf("enter the %d element:",(i+1));

arr[i]=sc.nextInt();

}

c1.sort(arr);

}

}