Counting Sort Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Counting Sort?

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

beginner

What kind of data is Counting Sort best suited for?

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

intermediate

Why does Counting Sort use an extra array for counts?

The extra array keeps track of how many times each number appears, helping to place each number directly in the sorted output.

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.

advanced

How does Counting Sort maintain stability (keeping equal elements in original order)?

By placing elements in the output array from right to left using the counts, Counting Sort keeps the original order of equal elements.

What does Counting Sort use to decide the position of each element?

A Swapping adjacent elements

B The count of each element

C Random selection

D Comparisons between elements

Counting Sort uses the count of each element to place it directly in the sorted output.

Which of these is a limitation of Counting Sort?

A It uses no extra memory

B It cannot sort negative numbers

C It is slower than bubble sort

D It only works with numbers in a small range

Counting Sort requires the input numbers to be in a small range to be efficient.

What is the space complexity of Counting Sort?

A O(n)

B O(k)

C O(n + k)

D O(1)

Counting Sort uses extra space for the count array and output array, totaling O(n + k).

How does Counting Sort handle duplicate elements?

A It counts duplicates and places them in order

B It ignores duplicates

C It swaps duplicates randomly

D It removes duplicates

Counting Sort counts duplicates and places each occurrence in the correct position.

Which step is NOT part of Counting Sort?

A Comparing elements pairwise

B Counting occurrences of each number

C Calculating cumulative counts

D Placing elements into output array

Counting Sort does not compare elements pairwise; it uses counts instead.

Explain how Counting Sort sorts an array step-by-step.

Think about counting first, then placing.

Describe when and why you would choose Counting Sort over other sorting algorithms.

Consider the data range and sorting speed.