Counting Sort | CrackEase

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 number of objects having each distinct key value, after this it performs 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 size = (max_element + 1) and initialize all counts to zero.
Count occurrences of each unique element and store at the corresponding index in the count array.
Convert the count array to cumulative counts (prefix sums) so each count[i] holds the position of the last occurrence of i in output.
Iterate the input array from right to left, place each element at output[count[element]-1], then decrement count[element].

Code

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

/*
 Note:
 - This C implementation uses variable length arrays (C99).
 - For portability to older compilers allocate dynamically (malloc) instead.
*/

void countSort(int array[], int size) {
    // find maximum element
    int max = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > max) max = array[i];
    }

    // create count and output arrays of appropriate size
    int count[max + 1];     // indices 0..max
    int output[size];

    // initialize counts to 0
    for (int i = 0; i <= max; ++i) count[i] = 0;

    // store count of each element
    for (int i = 0; i < size; i++) count[array[i]]++;

    // change count[i] so that count[i] contains actual position of this value in output[]
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];

    // build the output array (stable sort) - iterate from end to start
    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // copy the output array to array[], so that array[] now contains sorted items
    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>
#include <vector>
using namespace std;

void countSort(int array[], int size) {
    // find maximum element
    int max = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > max) max = array[i];
    }

    // use vectors for counts and output
    vector count(max + 1, 0);
    vector output(size);

    // store count of each element
    for (int i = 0; i < size; i++) count[array[i]]++;

    // cumulative counts
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];

    // build output (stable)
    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // copy back
    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;
}

  
// Counting sort in Java
class countSort {
    void applyCountSort(int array[], int size) {
        // find maximum element
        int max = array[0];
        for (int i = 1; i < size; i++) {
            if (array[i] > max) max = array[i];
        }

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

        // initialize counts (Java arrays default to 0 so this is optional)
        for (int i = 0; i <= max; i++) count[i] = 0;

        // store count of each element
        for (int i = 0; i < size; i++) count[array[i]]++;

        // cumulative count
        for (int i = 1; i <= max; i++) count[i] += count[i - 1];

        // build output array (stable) - iterate from end
        for (int i = size - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        // copy to original 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)

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Counting Sort

Counting Sort