Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.
Example :
Algorithm counting sort [A (0..n-1)]
// Sort a given array by Counting sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
countingSort(array, size)
max <- find largest element in array
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique element and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 1
#include < stdio.h >
#include < string.h >
void countsorting(int arr[], int n, int n1)
{
// creating an integer array of size n for sorted array
int outputArray[n];
// creating an integer array of size n1, initialized by zero
int freqArray[n1];
memset(freqArray, 0, sizeof(freqArray));
// Using the value of each item in an input array as index,
for (int i = 0; i < n; i++) {
freqArray[arr[i]]++;
}
// Calculating starting index for each integer
int totalCount = 0;
for (int i = 0; i < n1; i++)
{
int oldEleCount = freqArray[i];
freqArray[i] = totalCount;
totalCount += oldEleCount;
}
// Copying to output array, and preserving order of inputs with equal keys
for (int i = 0; i < n; i++)
{
outputArray[freqArray[arr[i]]] = arr[i];
freqArray[arr[i]]++;
}
// copying output array back to the input array
for (int i = 0; i < n; i++) {
arr[i] = outputArray[i];
}
}
int main()
{
int arr[] = { 4, 5, 2, 2, 1, 5, 4, 5, 6, 10, 10, 9, 10, 3, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int n1 = 11;
countsorting(arr, n, n1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Code
import java.util.Arrays;
class CountingSort {
void countSort(int arr[], int n) {
int[] arr1 = new int[n + 1];
int x = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > x)
x = arr[i];
}
int[] count_arr = new int[x + 1];
for (int i = 0; i < x; ++i) {
count_arr[i] = 0;
}
for (int i = 0; i < n; i++) {
count_arr[arr[i]]++;
}
for (int i = 1; i <= x; i++) {
count_arr[i] += count_arr[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
arr1[count_arr[arr[i]] - 1] = arr[i];
count_arr[arr[i]]--;
}
for (int i = 0; i < n; i++) {
arr[i] = arr1[i];
}
}
void display(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
public static void main(String args[]) {
int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
int n = arr.length;
CountingSort cs = new CountingSort();
cs.countSort(arr, n);
cs.display(arr);
}
}
Code
def countingSort(arr):
n = len(arr)
arr1 = [0] * n
x = [0] * 10
for i in range(0, n):
x[arr[i]] += 1
for i in range(1, 10):
x[i] += x[i - 1]
i = n - 1
while i >= 0:
arr1[x[arr[i]] - 1] = arr[i]
x[arr[i]] -= 1
i -= 1
for i in range(0, n):
arr[i] = arr1[i]
arr = [4, 2, 2, 8, 3, 3, 1]
countingSort(arr)
print(arr)
Code
2 3 1 8 3 4
1 2 2 3 3 4 8
best case, average case, worst case
Bucket sort
Heap sort