Page 132 - Data Structures Handout_Neat
P. 132
10.4 Non-Comparison Sorting
Unlike comparison-based algorithms (Bubble, Merge, Quick, Heap), which rely on
comparing elements to determine order, non-comparison sorting algorithms use properties
of the data itself to achieve sorting. These algorithms can achieve linear time complexity
( )under certain conditions, making them extremely efficient when applicable. However,
they are limited to specific types of data, such as integers within a known range.
The most common non-comparison sorting algorithms are Counting Sort and Radix
Sort. Both are widely used in practice when the dataset fits their constraints.
10.4.1 Counting Sort
Counting Sort works by counting the number of occurrences of each distinct element
in the array. It then uses this information to place elements directly into their correct
positions. This algorithm is efficient when the range of input values is not significantly larger
than the number of elements.
Key Points:
• Time complexity: ( + ), where is the range of input values.
• Stable if implemented carefully.
• Best suited for integers or categorical data with limited range.
Example: Counting Sort in C++
132
