Counting Sort Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Counting Sort Algorithm?

Counting Sort counts how many times each number appears, then uses these counts to place numbers in the right order without comparing them directly.

beginner

Which type of data is Counting Sort best suited for?

Counting Sort works best for sorting numbers that are small and within a known range, like ages from 0 to 100.

intermediate

What is the time complexity of Counting Sort and why?

Counting Sort runs in O(n + k) time, where n is the number of elements and k is the range of input values, because it counts and places elements without comparisons.

intermediate

How does Counting Sort ensure stability (keeping original order of equal elements)?

Counting Sort uses the counts to find exact positions for elements and places them from right to left, preserving the order of equal elements.

intermediate

What is a limitation of Counting Sort compared to comparison-based sorts?

Counting Sort needs extra space proportional to the range of input values, so it is not efficient if the range is very large compared to the number of elements.

What does Counting Sort use to sort elements?

A Counting how many times each value appears

B Comparing elements pairwise

C Swapping elements randomly

D Dividing elements into halves

Counting Sort counts the frequency of each value to sort without direct comparisons.

Which of these is a requirement for Counting Sort to work efficiently?

A Input must be floating point numbers

B Input must be already sorted

C Input values must be strings

D Input values must be integers within a small range

Counting Sort is efficient when input values are integers within a known small range.

What is the space complexity of Counting Sort?

A O(n + k), where k is the range of input values

B O(1), constant space

C O(n log n)

D O(n^2)

Counting Sort uses extra space proportional to the input size and the range of values.

How does Counting Sort place elements to maintain stability?

A By swapping elements randomly

B By placing elements from right to left using counts

C By sorting elements in reverse order

D By ignoring original order

Placing elements from right to left using counts keeps the original order of equal elements.

Counting Sort is NOT suitable when:

A The input contains only positive integers

B The input is small and within a small range

C The range of input values is very large

D The input is already sorted

A very large range makes Counting Sort use too much space and become inefficient.

Explain how Counting Sort works step-by-step on a small list of numbers.

Think about counting first, then using counts to find positions.

What are the advantages and disadvantages of Counting Sort compared to other sorting algorithms?

Consider speed and memory use.