CNTSORT - Editorial

editorial
,
1

Problem Link - Counting Sort Practice Problem in Jump from 2* to 3*

Problem Statement:

Given an array A of N integers, such that 1≤ A[i] ≤100, sort A in non-decreasing/ascending order, and display the elements of the sorted array.

Approach:

In this problem, you are asked to sort arrays using a specific sorting algorithm called Counting Sort.

Counting Sort is an integer sorting algorithm that operates by counting the occurrences of each unique value in the input array. Given that the values in the array are limited to the range 1 through 100, we can directly use an auxiliary array (let’s call it count) to count the occurrences of each number in that range.

The steps for Counting Sort are as follows:

  1. Count Occurrences: Create a count array of size 101 (since values range from 1 to 100). Each index i of the count array will store the frequency of the number i.
  2. Populate the Count Array: Traverse the input array and increment the respective index in the count array for each element.
  3. Reconstruct the Sorted Array: After populating the count array, iterate through the count array and reconstruct the sorted array by outputting each number according to its frequency.

Complexity:

  • Time Complexity: O(N+K), where N is the number of elements in the array and K is the range of numbers. Since K is constant (100), this simplifies to O(N) for each test case.
  • Space Complexity: O(K), which is O(100), so it’s constant space for our case.