# Counting Sort

**Counting Sort**: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the array, and stores these same elements in the auxiliary array. It was developed by **Harold H. Seward** in **1954**.

### Complexity table of counting sort

Complexity | Best case | Average case | Worst case |

Time | ? (n + k) | ? (n + k) | O (n + k) |

Space | O S(nk) |

Where** n** is the number of the element, and **k** is the range of the input.

### Algorithm of counting sort

Counting_Sort (array, size) max ? find the largest element from the array. define count array length [largest + 1]. for i ? 0 to max do count[i] = 0 // initialize count array with all zeros. for i ? 1 to size do increase count of each number which has found in the array. for i ? 1 to max do count[i] = count[i] + count[i+1] // cumulative sum. for i ? size to 1 decrease by 1 do store the number in the output array. decrease count[i] done return the output array End

**Example 1: **Suppose we have the following array, which we have to sort.

5 | 5 | 4 | 1 | 8 | 2 | 2 | 3 |

**Step 1:** Find the largest element in the given array.

Largest element is = 8 **5** **5** **4** **1** **8** **2** **2** **3**

**Step 2: **Initialize a new array, and the size of the new array is (Largest + 1).

**Step 3:** Count each element in the given array, and stores the element at their respective index in the count array. For example: If 5 is assigned 2 times to the original array, then 2 will be stored at the 5th position in the count array. If 6 is assigned 0 times, then 0 will be stored at the 6th position in the count array.

**Step 4:** Make the cumulative sum of the elements of the count array. This helps to place the elements in the correct index of the sorted array.

**Step 5: ** This process will be implemented throughout the array.

**Counting sort program in C language:**

#include <stdio.h> void countingSort(int array[], int size) { int output[10]; int max = array[0]; for (int i = 1; i < size; i++) { if (array[i] > max) max = array[i]; } int count[10]; for (int i = 0; i <= max; ++i) { count[i] = 0; } for (int i = 0; i < size; i++) { count[array[i]]++; } for (int i = 1; i <= max; i++) { count[i] += count[i - 1]; } for (int i = size - 1; i >= 0; i--) { output[count[array[i]] - 1] = array[i]; count[array[i]]--; } for (int i = 0; i < size; i++) { array[i] = output[i]; } } // Function to print an array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } // Driver code int main() { int array[] = {5, 5, 4, 1, 3, 8}; int n = sizeof(array) / sizeof(array[0]); countingSort(array, n); printArray(array, n); }