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

Counting-Based Sorting

Explore counting-based sorting algorithms including counting-sort and radix-sort designed for sorting small integers efficiently. Understand how these algorithms use indexing and stability properties to achieve faster sorting than comparison-based methods. Learn their implementations, time complexities, and practical applications in Java data structures.

We'll cover the following...

In this section, 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 a as indexes to 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 a 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]. ...