Data Structure Counting Sort Practice Questions with Solutions

By /

Introduction

Counting Sort is a sorting algorithm that works by counting how many times each value appears in an array. Instead of comparing elements with each other, it uses a counting array to store frequencies and then rebuilds the sorted array. It works especially well when the range of input values is relatively small. In this chapter, you will practice Counting Sort with JavaScript through 10 solved questions covering frequency counting, ascending and descending sorting, duplicates, ranges, and reusable functions. Data Structure Counting Sort practice questions with solutions help to understand the concepts.

Question 1: Sort an Array Using Counting Sort

Question

Sort the following array in ascending order using Counting Sort:

let numbers = [4, 2, 2, 8, 3, 3, 1];

Solution

function countingSort(arr) {
    let max = Math.max(...arr);

    let count = new Array(max + 1).fill(0);

    for (let number of arr) {
        count[number]++;
    }

    let result = [];

    for (let i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            result.push(i);
            count[i]--;
        }
    }

    return result;
}

let numbers = [4, 2, 2, 8, 3, 3, 1];

console.log(countingSort(numbers));

Output

[1, 2, 2, 3, 3, 4, 8]

The count array stores how many times each number occurs.

Question 2: Create a Frequency Count Array

Question

Create a counting array for:

let numbers = [2, 4, 2, 1, 3, 4, 2];

Solution

let numbers = [2, 4, 2, 1, 3, 4, 2];

let max = Math.max(...numbers);
let count = new Array(max + 1).fill(0);

for (let number of numbers) {
    count[number]++;
}

console.log(count);

Each index represents a number, and its value represents its frequency.

For example:

Index:  0  1  2  3  4
Count:  0  1  3  1  2

Output

[0, 1, 3, 1, 2]

This tells us:

1 → appears 1 time
2 → appears 3 times
3 → appears 1 time
4 → appears 2 times

Question 3: Sort Numbers in Descending Order

Question

Use Counting Sort to arrange these numbers from largest to smallest:

let numbers = [3, 6, 4, 1, 3, 4, 2];

Solution

function countingSortDescending(arr) {
    let max = Math.max(...arr);

    let count = new Array(max + 1).fill(0);

    for (let number of arr) {
        count[number]++;
    }

    let result = [];

    for (let i = count.length - 1; i >= 0; i--) {
        while (count[i] > 0) {
            result.push(i);
            count[i]--;
        }
    }

    return result;
}

let numbers = [3, 6, 4, 1, 3, 4, 2];

console.log(countingSortDescending(numbers));

Output

[6, 4, 4, 3, 3, 2, 1]

The only major change is that we traverse the counting array from the highest index to the lowest.

Question 4: Find the Most Frequently Occurring Number

Question

Using the counting technique, find the number that occurs most often:

let numbers = [1, 3, 2, 3, 4, 3, 2, 1, 3];

Solution

let numbers = [1, 3, 2, 3, 4, 3, 2, 1, 3];

let max = Math.max(...numbers);
let count = new Array(max + 1).fill(0);

for (let number of numbers) {
    count[number]++;
}

let mostFrequent = 0;

for (let i = 1; i < count.length; i++) {
    if (count[i] > count[mostFrequent]) {
        mostFrequent = i;
    }
}

console.log("Most frequent number:", mostFrequent);
console.log("Frequency:", count[mostFrequent]);

Output

Most frequent number: 3
Frequency: 4

The number 3 occurs four times, which is more than any other value.

Question 5: Count the Number of Distinct Values

Question

Use a counting array to find how many different values exist in:

let numbers = [4, 2, 4, 1, 2, 5, 1, 3];

Solution

let numbers = [4, 2, 4, 1, 2, 5, 1, 3];

let max = Math.max(...numbers);
let count = new Array(max + 1).fill(0);

for (let number of numbers) {
    count[number]++;
}

let distinct = 0;

for (let i = 0; i < count.length; i++) {
    if (count[i] > 0) {
        distinct++;
    }
}

console.log("Distinct values:", distinct);

Output

Distinct values: 5

The distinct values are:

1, 2, 3, 4, 5

Question 6: Sort an Array When Values Have a Small Range

Question

Sort the following array using Counting Sort:

let numbers = [1, 0, 2, 1, 2, 0, 1, 2];

Solution

function countingSort(arr) {
    let max = Math.max(...arr);

    let count = new Array(max + 1).fill(0);

    for (let number of arr) {
        count[number]++;
    }

    let result = [];

    for (let i = 0; i < count.length; i++) {
        for (let j = 0; j < count[i]; j++) {
            result.push(i);
        }
    }

    return result;
}

let numbers = [1, 0, 2, 1, 2, 0, 1, 2];

console.log(countingSort(numbers));

Output

[0, 0, 1, 1, 1, 2, 2, 2]

Counting Sort is particularly convenient when the possible values are limited to a small range such as 0, 1, and 2.

Question 7: Find the Smallest and Largest Value Using Counting

Question

Use the counting array to find the smallest and largest values in:

let numbers = [7, 4, 9, 2, 5, 2, 8];

Solution

let numbers = [7, 4, 9, 2, 5, 2, 8];

let max = Math.max(...numbers);
let count = new Array(max + 1).fill(0);

for (let number of numbers) {
    count[number]++;
}

let smallest = -1;
let largest = -1;

for (let i = 0; i < count.length; i++) {
    if (count[i] > 0) {
        smallest = i;
        break;
    }
}

for (let i = count.length - 1; i >= 0; i--) {
    if (count[i] > 0) {
        largest = i;
        break;
    }
}

console.log("Smallest:", smallest);
console.log("Largest:", largest);

Output

Smallest: 2
Largest: 9

The first occupied position gives the smallest value, while the last occupied position gives the largest value.

Question 8: Sort Student Marks Using Counting Sort

Question

Sort these marks in ascending order using Counting Sort:

let marks = [75, 82, 75, 90, 68, 82, 95];

Solution

function countingSort(arr) {
    let min = Math.min(...arr);
    let max = Math.max(...arr);

    let count = new Array(max - min + 1).fill(0);

    for (let number of arr) {
        count[number - min]++;
    }

    let result = [];

    for (let i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            result.push(i + min);
            count[i]--;
        }
    }

    return result;
}

let marks = [75, 82, 75, 90, 68, 82, 95];

console.log(countingSort(marks));

Output

[68, 75, 75, 82, 82, 90, 95]

Here, min is used to reduce the size of the counting array because the values do not start from zero.

Question 9: Count How Many Values Occur More Than Once

Question

Use Counting Sort’s counting technique to find how many values appear at least twice:

let numbers = [2, 5, 2, 7, 5, 8, 5, 9, 2];

Solution

let numbers = [2, 5, 2, 7, 5, 8, 5, 9, 2];

let max = Math.max(...numbers);
let count = new Array(max + 1).fill(0);

for (let number of numbers) {
    count[number]++;
}

let repeatedValues = 0;

for (let i = 0; i < count.length; i++) {
    if (count[i] >= 2) {
        repeatedValues++;
    }
}

console.log("Values appearing at least twice:", repeatedValues);

Output

Values appearing at least twice: 2

The values are:

2 → 3 times
5 → 3 times

So there are 2 values that appear at least twice.

Question 10: Create a Reusable Counting Sort Function

Question

Create a reusable Counting Sort function and use it to sort:

[9, 4, 1, 7, 4, 2]

and

[6, 3, 8, 2, 5, 3]

Solution

function countingSort(arr) {
    if (arr.length === 0) {
        return [];
    }

    let min = Math.min(...arr);
    let max = Math.max(...arr);

    let count = new Array(max - min + 1).fill(0);

    for (let number of arr) {
        count[number - min]++;
    }

    let result = [];

    for (let i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            result.push(i + min);
            count[i]--;
        }
    }

    return result;
}

let numbers1 = [9, 4, 1, 7, 4, 2];
let numbers2 = [6, 3, 8, 2, 5, 3];

console.log(countingSort(numbers1));
console.log(countingSort(numbers2));

Output

[1, 2, 4, 4, 7, 9]
[2, 3, 3, 5, 6, 8]

The function can now be reused with different integer arrays.

Key Takeaways

  • Counting Sort sorts values by using their frequency.
  • It does not compare elements like Bubble Sort or Quick Sort.
  • A counting array stores how many times each value occurs.
  • Duplicate values are naturally handled by their frequencies.
  • Counting Sort works especially well when the input range is small.
  • The counting array can be traversed forward for ascending order.
  • The counting array can be traversed backward for descending order.
  • Counting Sort can also help find frequencies, repeated values, and distinct values.
  • With a suitable offset, the algorithm can handle values that do not start from zero.
  • Its typical time complexity is O(n + k), where n is the number of elements and k is the value range.
  • Its space complexity is generally O(n + k) for implementations that build an output array.
  • Counting Sort is most effective when k is not excessively large compared with n.

FAQs

1. What is Counting Sort in Data Structures?

Counting Sort is a sorting algorithm that counts the frequency of each value and uses those counts to construct the sorted result.

2. Does Counting Sort compare elements?

No. Unlike comparison-based sorting algorithms, Counting Sort primarily uses the values as indexes in a counting array.

3. What is the time complexity of Counting Sort?

The typical time complexity is O(n + k), where n is the number of input elements and k represents the range of values.

4. When should Counting Sort be used?

Counting Sort is useful when the input contains integers and the range of possible values is relatively small.

5. Can Counting Sort handle duplicate values?

Yes. Duplicate values are handled by increasing their frequency in the counting array.

6. Can Counting Sort sort negative numbers?

Basic Counting Sort is usually designed for non-negative integers, but negative values can be supported by using an offset based on the minimum value.

7. What is the main disadvantage of Counting Sort?

Counting Sort can require a large amount of memory when the range of possible values is very large compared with the number of elements.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top