by BehindJava

# Data Structures - Radix Sort Algorithm

Home » datastructures » Data Structures - Radix Sort Algorithm

In this tutorial, we are going to learn about radix sort in detail and its algorithmic implementation.

• Counting sort is often used as the sort algorithm for radix sort - must be stable counting sort.
• O(n) - can achieve this because we’re making assumptions about the data we’re sorting.
• Even so, it often runs slower than O(n log n) algorithms because of the overhead involved.
• In-place depends on which sort algorithm you use.
• Stable algorithm.

• Makes assumptions about the data.
• Data must have same radix and width.
• Because of this, data must be integers or strings.
• Sort based on each individual digit or letter position.
• Start at the rightmost position.
• Must se a stable sort algorithm at each stage.

2. max = largest element in the given array
3. d = number of digits in the largest element (or, max). Now, create d buckets of size 0 - 9
4. for i -> 0 to d. sort the array elements using counting sort (or any stable sort) according to the digits at
the ith place.

# Radix Sort Programmatic Implementation in Java

``````public class RadixSort {
public static void main(String[] args) {

int[] radixArray = { 4725, 4586, 1330, 8792, 1594, 5729 };

for (int i = 0; i < radixArray.length; i++) {
}
}

for (int i = 0; i < width; i++) {
}
}

int numItems = input.length;

for (int value : input) {
}
for (int j = 1; j < radix; j++) {
countArray[j] += countArray[j - 1];
}
int[] temp = new int[numItems];
for (int tempIndex = numItems - 1; tempIndex >= 0; tempIndex--) {
``1330 1594 4586 4725 5729 8792 ``