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

Recall & Review

beginner

What is the main idea behind Radix Sort Algorithm?

Radix Sort sorts numbers by processing individual digits. It starts from the least significant digit and moves to the most significant digit, grouping numbers by each digit at every step.

beginner

Which data structure is commonly used inside Radix Sort to group numbers by digits?

Queues or buckets are used to group numbers by their current digit during each pass of Radix Sort.

intermediate

Why does Radix Sort work efficiently on fixed-length integers?

Because it processes digits one by one, the number of passes depends on the number of digits, which is fixed for fixed-length integers, making the sorting time predictable and efficient.

intermediate

What is the time complexity of Radix Sort for n numbers with d digits each?

The time complexity is O(d * (n + k)), where n is the number of elements and k is the range of digits (usually 10 for decimal digits).

advanced

Can Radix Sort be used for sorting strings? If yes, how?

Yes, Radix Sort can sort strings by processing characters from the least significant position (rightmost character) to the most significant (leftmost), grouping strings by characters at each position.

What is the first digit Radix Sort processes when sorting numbers?

A Least significant digit

B Most significant digit

C Middle digit

D Random digit

Radix Sort starts sorting from the least significant digit to ensure correct order after all passes.

Which data structure is typically used to hold numbers during each digit grouping in Radix Sort?

A Stack

B Tree

C Queue

D Hash Map

Queues are used to maintain the order of numbers grouped by digits during each pass.

What is the main advantage of Radix Sort over comparison-based sorts like QuickSort?

A It sorts in place

B It has better average case time complexity for fixed digit sizes

C It uses less memory

D It works only on strings

Radix Sort can sort in linear time relative to number of digits and elements, which can be faster than comparison sorts for fixed digit sizes.

What is the time complexity of Radix Sort if n is the number of elements and d is the number of digits?

A O(n log n)

B O(log n)

C O(n^2)

D O(d * n)

Radix Sort runs in O(d * n) time, processing each digit for all elements.

Radix Sort is best suited for which type of data?

A Fixed-length integers or strings

B Floating point numbers

C Linked lists

D Unsorted graphs

Radix Sort works best on fixed-length integers or strings where digits or characters can be processed uniformly.

Explain step-by-step how Radix Sort sorts the array [170, 45, 75, 90, 802, 24, 2, 66].

Think about sorting by units, then tens, then hundreds place.

Describe the difference between Radix Sort and comparison-based sorting algorithms.

Focus on how sorting decisions are made.