what is count sort?
a.) It is a sorting algorithm that sorts in linear time.
b.) It makes no comparisons between the elements
c.) It works as follows :
Input : A[1...n], where A[j]€ {1,2,…k}
Output : B[1...n], sorted
Auxillary Storage : C[1...k]
The algorithm
for i <– 1 to k
do C[i] <– 0
for j <– 1 to n
do C[A[j]] <– C[A[j]] + 1
for i <– 2 to k
do C[A[i]] <– C[i] + C[i-1]
for j <– n downto 1
do B[C[A[j]]] <– A[j]
C[A[j]] <– C[A[j]] -1
Analysis of algorithm
| Data structure: | Array |
| Worst case performance: | O(n + k) |
| Best case performance: | O(n + k) |
| Average case performance: | O(n + k) |
Program
package com.bundle.algos;
public class CountingSort {
public static void main(String args[]){
//int[] _array = new int[]{2,5,3,0,2,3,0,3};
//int[] _array = new int[]{2,5,3,6,1,3,0,3};
int[] _array = new int[]{4,1,3,4,3};
//int[] _array = new int[]{};
if(_array.length == 0){
System.out.println(“Array is empty”);
}else if(_array.length == 1){
System.out.println(“Just one element, array is already sorted”);
}else{
int min = _array[0];
int max = _array[0];
for(int i=1;i<_array.length;i++){
if(_array[i] <= min){
min = _array[i];
}else if(_array[i] > max){
max = _array[i];
}
}
System.out.println(“minimum = ” + min + “, maximum = ” + max + “, No. of elements = ” + _array.length + “, Range = ” + min + “-” + max);
countSort(_array,min,max);
}
}
public static void countSort(int[] A,int low,int high){
int cRange = high-low+1;
int[] C = new int[cRange+1];
int[] B = new int[A.length+1];
for(int i=0;i<=high;i++){
C[i]=0;
}
for(int j=0;j<=A.length-1;j++){
C[A[j]] = C[A[j]] + 1;
}
for(int i=low;i<= high;i++){
System.out.println(“C["+i+"] = ” + C[i]);
}
for(int j=1;j<=high;j++){
C[j] = C[j] + C[j-1];
}
for(int j=0;j<A.length;j++){
B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]] -1;
}
for(int i=1;i<B.length;i++){
System.out.println(“B["+i+"] = ” + B[i]);
}
}
}
