Counting Sort in C++

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++

#include <iostream>
using namespace std;

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

  //Find the largest element of the array
  for (int i = 1; i < size; i++) 
  {
    if (array[i] > max)
      max = array[i];
  }

  //Initializing count array with zeros.
  for (int i = 0; i <= max; ++i) 
  {
    count[i] = 0;
  }

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

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

  /*Finding the index of each element of the original 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]]--;
  }

 
  for (int i = 0; i < size; i++) {
    array[i] = output[i];
  }
}

//printing function
void display(int array[], int size) 
{
  for (int i = 0; i < size; i++)
    cout << array[i] << "\t";
  cout << endl;
}


int main() 
{
  int array[] = {2, 5, 2, 8, 1, 4, 1};
  int n = sizeof(array) / sizeof(array[0]);
  cout<<"Unsorted array\n";
  display(array, n);
  countSort(array, n);
  cout<<"Sorted array\n";
  display(array, n);
}
Output:
Unsorted array
2	5	2	8	1	4	1	
Sorted array
1	1	2	2	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