Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Counting-Based Sorting

Explore the counting-sort and radix-sort algorithms designed for sorting integers efficiently by using element values as array indexes. Learn how counting-sort provides a stable sorting method with linear time complexity, and how radix-sort extends this approach to handle large integers by processing bits in multiple passes. This lesson helps you implement and understand non-comparison based sorting for performance optimization in C++.

We'll cover the following...

In this lesson, we study two sorting algorithms that are not comparison based. Specialized for sorting small integers, these algorithms elude the lower bounds of Theorem 1 in the previous lesson by using (parts of) the elements in as indexes into an array. Consider a statement of the form

c[a[i]]=1c[a[i]] = 1

This statement executes in constant time, but has c.length possible different outcomes, depending on the value of a[i]. This means that the execution of an algorithm that makes such a statement cannot be modeled as a binary tree. Ultimately, this is the reason that the algorithms in this section are able to sort faster than comparison-based algorithms.

Counting-sort

Suppose we have an input array a consisting of nn integers, each in the range 0,...,k−10,...,k − 1. The counting-sort algorithm sorts aa using an auxiliary array c of counters. It outputs a sorted version of a as an auxiliary array b.

The idea behind counting-sort is simple: for each i∈{0,...,k−1}i \in \{0,...,k − 1\}, count the number of occurrences of i in a and store this in c[i]. ...