Counting Sort in C++

June 4, 2022

What is counting sort in C++?

Counting sort is a sorting algorithm that sorts the elements in a logical order, of an array by counting the number of time of each unique element is present in the array. Then using the count of each unique element we can sort them in a stored order in another array. It is used as a sub-routine to another sorting algorithm like radix sort. In this article, we will learn more about counting sort in C++.

Counting sort algorithm in C++

Working of counting sort in C++

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.

 

Counting Sort in C++

Algorithm for counting sort in C++

Counting Sort (array P, array Q, int k)
1. For i ← 1 to k
2. do C [i] ← 0 [ θ(k) times]
3. for j ← 1 to length [A]
4. do C[A[j]] ← C [A [j]]+1 [θ(n) times]
// C [i] now contain the number of elements equal to i
5. for i ← 2 to k
6. do C [i] ← C [i] + C[i-1] [θ(k) times]
//C[i] now contain the number of elements ≤ i
7. for j ← length [A] down to 1 [θ(n) times]
8. do B[C[A[j] ← A [j]
9. C[A[j] ← C[A[j]-1

Program for counting sort in C++

Run 
// 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;
}

Output

1 1 2 2 3 4 5 8

Time Complexity
For Counting sort in C++

Best

O(n + k)

Average

O(n + k)

Worst

O(n + k)

Quiz time

Quiz Time

Question 1.Which of the following sorting algorithms in its typical implementation gives best performance when applied on a sorted array?

  1. Quick Sort
  2. Heap Sort
  3. Insertion Sort
  4. Merge
Insertion sort takes linear time when input array is sorted or almost sorted. All other sorting algorithms mentioned above will take more than linear time in their typical implementation.
 
Ans. Insertion Sort (C)
 

Question 2. What is the time complexity of Build Heap operation. Which is used to create a max(or min) binary heap from a given array.?

  1. O(n)
  2. O(log n)
  3. O(nlog n)
  4. None of the above
BUILD-HEAP(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do HEAPIFY(A, i); 
    end for 
END

Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).

Ans: A

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting