Counting Sort

Counting Sort, is an integer sorting algorithm, is a sorting technique in which we sort a collection of elements based on numeric keys between the specific range. In the counting algorithm we don’t compare element while sorting.it is often used as a subroutine in other sorting algorithm. By counting It operates the no. of objects having each distinct key value, after this it perform some arithmetic to calculate the position of each key value in output sequence.

It is used as a subroutine in another sorting algorithm for example radix sort.

If we compare counting sort to bucket sort then we see that bucket sort requires a large amount of preallocated memory or linked list and dynamic array to hold the sets of items within each bucket, whereas counting sort instead stores a single number per bucket.

How it works?

To sort any list into a logical order using counting sort following steps are followed :-

Create a count array with value of every index equal to zero of size one greater then the maximum element in the array.
Now store the count of each unique element at their respective index.
Sorting of array is done with the help of total count, so store the total or cumulative sum of the elements of the count array.
Place each element from the array in position equal to its count-1.
Decrease the count of element placed by 1.

Code

  
// Counting sort in C programming
#include<stdio.h>
#define MAX 255

void countSort(int array[], int size) {
    int output[MAX];
    int count[MAX];
    int max = array[0];

    // Here we find the largest item in the array
    for (int i = 1; i < size; i++) { if (array[i] > max)
            max = array[i];
    }

    // Initialize the count for each element in array to 0
    for (int i = 0; i <= max; ++i) {
        count[i] = 0;
    }

    // For each element we store the count
    for (int i = 0; i < size; i++) {
        count[array[i]]++;
    }

    // Store the cummulative count of each array
    for (int i = 1; i <= max; i++) 
    { 
        count[i] += count[i - 1]; 
    } 

    // Search the index of each element of the actual array in count array, and 
    // place the elements in output array 
    for (int i = size - 1; i >= 0; i--) 
    {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // Transfer the sorted items into actual array
    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

// printing items of the array
void display(int array[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ",array[i]);
    printf("\n");
}

// Driver code
int main() {
    int array[] = {2, 5, 2, 8, 1, 4, 1};
    int n = sizeof(array) / sizeof(array[0]);
  
    countSort(array, n);
  
    display(array, n);

    return 0;
}

  
// Counting sort in C++ programming
#include<iostream>
#define MAX 255
using namespace std;

void countSort(int array[], int size) {
    int output[MAX];
    int count[MAX];
    int max = array[0];

    // Here we find the largest item in the array
    for (int i = 1; i < size; i++) { if (array[i] > max)
            max = array[i];
    }

    // Initialize the count for each element in array to 0
    for (int i = 0; i <= max; ++i) {
        count[i] = 0;
    }

    // For each element we store the count
    for (int i = 0; i < size; i++) {
        count[array[i]]++;
    }

    // Store the cummulative count of each array
    for (int i = 1; i <= max; i++) 
    { 
        count[i] += count[i - 1]; 
    } 

    // Search the index of each element of the actual array in count array, and 
    // place the elements in output array 
    for (int i = size - 1; i >= 0; i--) 
    {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // Transfer the sorted items into actual array
    for (int i = 0; i < size; i++) {
        array[i] = output[i];
    }
}

// Function to print an array
void display(int array[], int size) {
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int array[] = {2, 5, 2, 8, 1, 4, 1};
    int n = sizeof(array) / sizeof(array[0]);
  
    countSort(array, n);
  
    display(array, n);

    return 0;
}

  
class countSort {
    void applycountSort(int array[], int size) {
        int[] output = new int[size + 1];

        // Here we find the largest item in the array
        int max = array[0];
        for (int i = 1; i < size; i++) { if (array[i] > max)
                max = array[i];
        }
        int[] count = new int[max + 1];

        // Initialize the count for each element in array to 0
        for (int i = 0; i < max; ++i) {
            count[i] = 0;
        }

        // For each element we store the count
        for (int i = 0; i < size; i++) {
            count[array[i]]++;
        }

        // Store the cummulative count of each array
        for (int i = 1; i <= max; i++) 
        { 
            count[i] += count[i - 1]; 
        } 

        // Search the index of each element of the actual array in count array, and 
        // place the elements in output array 
        for (int i = size - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        // Transfer the sorted items into actual array
        for (int i = 0; i < size; i++) {
            array[i] = output[i];
        }
    }
    
    // printing items of the array
    static void display(int array[], int size) {
    for (int i = 0; i < size; i++)
        System.out.print(array[i] + " ");
    System.out.println();
}


    // Driver code
    public static void main(String args[]) {
        int[] data = {2, 5, 2, 8, 1, 4, 1};
        int size = data.length;

        countSort obj = new countSort();
        obj.applycountSort(data, size);
        
        display(data,size);
    }
}

	
1 1 2 2 4 5 8

Time Complexity for Counting Sort

Best	Average	Worst
O(n + k)	O(n + k)	O(n + k)

→

←

Courses

Chapters

Aptitude

Sorting

Linked List

Stack

Queue

Tree

Counting Sort

Counting Sort