Counting Sort in C++

Counting Sort in c++ is a sorting algorithm used to sort an array using a counting array.

Counting sort is efficient to use in when

  • values of element lie in the small range.
  • the values are non-negative.

Counting Sort Algorithm

Counting array– It is the array which stores the counts of occurrence of each value.

For example in our case:

Array values ranging from 2 to 15

  1. Count the occurrence of value in the array and store it in counting Array.
  2. Track the counting array and rewrite the original array.

Counting Sort Code

Online Compiler

Output

Overview of Counting Sort

  • Not an in-place algorithm (requres an extra array i.e counting array).
  • O(n)-complexity.
  • To make it a stable sort, some extra steps are needed.

Also check Insertion sort in C++.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.