1. Introduction
Sorting algorithms were devised in order to make the ordering of elements of a list or array possible. There are many available to choose from, such as Bubble Sort, Quick Sort, Selection Sort, Heap Sort, Merge Sort, just to name a few. Radix Sort is a sorting algorithm that just happens to be fairly efficient. This article will explore the Radix Sort. There will also be an implementation of the Radix Sort in Java.
2. Why Radix Sort ?
Many sorts have exponential time complexities, such as Bubble Sort, Quick Sort, Selection Sort, and Insertion Sort. Radix Sort has linear time complexities. This means that as the number of elements increases the time to accomplish the sorting will be proportional to the number of elements. In contrast, with sorts with exponential time complexities, the time to accomplish the sorting could be as bad as the number of elements raised to the second power, so the time will increase faster than with linear time complexity.
3. Radix Sort vs sorts with exponential time complexity
Radix Sort is able to make various passes through depending on the maximum length of the largest element to be sorted in a list or array. Thus Radix Sort is said to have “kn” where k is the length of the largest element and n is the number of elements. For example, with Radix Sort, if there are 20 elements, and the largest element is 4 digits, it will take 4*20 or 80 time units. For a comparable exponential time complexity sorting algorithm, it will take n^2 or 20*20 = 400 time units, which makes Radix Sort 5 times more time-efficient. For 1000, elements, Radix Sort gives us 1000*4 = 4000 time units, as opposed to exponential time complexities, 1000^2 = 1 000 000 time units. That is a factor of 250.
4. How Radix Sort is able to achieve linear time complexity
Exponential Sorts normally accomplish the ordering by comparing each element with every other element. Radix Sort accomplishes the ordering by placing each element into buckets based on the value of a positional digit or character. The count of the elements in that bucket will be used to offset the element in the resulting list or array.
5. Defining Digits
For numeric arrays such as arrays of integers and floats, we can use a single digit to determine the order of the elements. For string arrays, we can choose the ascii values of each character, which are normally 2 or 3 digits. The choice of a single digit or multiple digits is known as the defining digits for the Radix Sort.
6. The Radix Sort sorting algorithm
Pre-sort
1 – Create a result array from the original array. Items from the original array will be copied to the result array for each pass through the original array. The resulting array and the original array must be the same size.
2 – Prepare the original array:
a – integer array – to properly sort negative numbers, add the absolute value of the smallest number (most negative).
For arrays with only positive and zero integers, no adjustment to the original need to be made.
b – float array – convert float to integer by multiplying each element
by 1000. This allows for ame method for counting occurrences of digit
as for integer.
c – string array – make sure each element is the same length. This is done by
determining the longest string and padding each element with trailing spaces.
(NOTE: padding with spaces only produces the right order if used with alphanumeric strings)
Sort
3 – Create a bucket array
a – float array and integer array – an array of 10 (base 10) to store the counts for each digit under consideration.
b – string array – counts for ascii value of each character, 255 max length. This can be specialized if strings are only alphanumeric characters.
4 – Loop from right-most character for string or digit for integer and float:
a – initialize bucket array, so counts are zeroed out
b – for each element of the array, increment count of this digit or character in bucket array
c – when the sum of counts in bucket array is equal to number of elements in original array
add a running sum of the counts in the bucket array, starting from element 1
The last element in the bucket array should be equal to the number of elements in the
original array
d – create the sorted positional array, but starting from the last element of the array.
use the bucket array to determine the offset from the beginning and add the element to
that location decrement that offset by one.
continue until all of the sorted positional array is completed.
Post-sort
5 – Add transformation to the sorted array to restore the original value format if necessary.
a – for integer array, if values were previously added to convert array to a non-negative array, apply these values in reverse
b – for float array, divide the result array (in integers) by 1000 to restore the original decimal places
c – for string array, strip out the trailing spaces which was previously appended to the make all the strings the same length.
7. Example
The data used in this example was generated randomly by the program itself. Each run of the program would be working on a unique set of input data. This code can be easily modified to use a specific or static array of data.
7.1.1 Sorting Integers
This example implements the radix sort for integers by first converting all integers to non-negative integers by adding the absolute value of the largest negative integer, performing the sort, and finally subtracting from each non-negative integer the same factor that was previously added.
7.1.2 Sorting Floats
The implementation for floats was first done by eliminating the decimal point by multiplying each float by 10000 to convert it to an integer. Then the sort was performed by using the method described in the previous paragraph. The resulting integer array was divided by 10000 to restore the original float numbers. It was determined that 4 decimal places were used by floats in Java.
7.1.3 Sorting Strings
Finally, for a radix sort on strings to be performed, all strings were converted to same length strings by right padding with spaces. Then the characters making up the strings were used to define the buckets by their ascii values starting from the right-most characters moving towards the left-most characters.
7.2.1 Source Code
import java.util.Arrays;
import java.util.Random;
public class RadixSort {
final static int numberOfElements = 10;
final static int base = 10;
public static void radixSortForIntegersByPlaceWithBase(int [] original, int [] sorted, int place) {
int [] bucket = new int[base];
Arrays.fill(bucket, 0);
for (int i = 0; i < original.length; i++) {
bucket[(original[i] / place) % base]++;
}
for (int i = 1; i < bucket.length; i++) {
bucket[i] += bucket[i-1];
}
for (int i = original.length-1 ; i >= 0; i--) {
sorted[--bucket[(original[i] / place) % base]] = original[i];
}
}
public static void radixSortForIntegersByPlace(int [] original, int [] sorted, int maxNumber) {
int multiplier = 1;
while (multiplier <= maxNumber) {
radixSortForIntegersByPlaceWithBase(original, sorted, multiplier);
for (int i = 0; i < sorted.length; i++) {
original[i] = sorted[i];
}
multiplier *= base;
}
}
public static float [] getFloatArray() {
final int maxValue = 2000000;
float [] array = new float[numberOfElements];
Random rand = new Random();
for (int i = 0; i < numberOfElements; i++) {
int decimalPoints = rand.nextInt(3)+1;
boolean sign = rand.nextBoolean();
int nextInt = rand.nextInt(maxValue);
array[i] = (nextInt / (float)Math.pow(base, decimalPoints)) * (sign ? 1: -1);
}
return array;
}
public static int [] getIntArray() {
final int maxValue = 200 * base;
int [] intArray = new int[numberOfElements];
Random rand = new Random();
for (int i = 0; i < numberOfElements; i++) {
boolean sign = rand.nextBoolean();
int nextInt = rand.nextInt(maxValue);
intArray[i] = nextInt * (sign ? 1: -1);
}
return intArray;
}
public static String getStringOfLength(int maxStrLength, String type) {
Random rand = new Random();
String str = "";
int minValue = 32;
int maxValue = 127;
int strSize = rand.nextInt(maxStrLength);
while (str.length() < strSize) {
int ascii = rand.nextInt(255)+1;
if (type.contentEquals("alphanumeric")) {
if (ascii == ' ' || (ascii >= 'a' && ascii <= 'z') ||
(ascii >= 'A' && ascii <= 'Z') ||
(ascii >= '0' && ascii <= '9')
)
str += (char)(ascii);
} else if (ascii >= minValue && ascii < maxValue)
str += (char)(ascii);
}
return str;
}
public static String getAlphanumericStringOfLength(int maxStrLength) {
return getStringOfLength(maxStrLength, "alphanumeric");
}
public static String [] getStringArray() {
final int maxStringSize = 15;
String [] strArray = new String[numberOfElements];
for (int i = 0; i < numberOfElements; i++) {
strArray[i] = getAlphanumericStringOfLength(maxStringSize);
}
return strArray;
}
public static void printBanner(String label) {
int bannerLength = 110;
StringBuffer stars = new StringBuffer();
StringBuffer dashes = new StringBuffer();
String descformat = "%" + String.format("%d", (bannerLength-label.length())/2 + label.length()) + "s\n";
for (int i = 0; i < bannerLength; i++) stars.append('*');
for (int i = 0; i < bannerLength; i++) dashes.append('-');
System.out.println(stars);
System.out.printf(descformat, label);
System.out.println(dashes);
}
public static void printFloatArray(float [] array, String label) {
StringBuffer sb = new StringBuffer();
for (float num: array) {
if (sb.length() > 0)
sb.append(", ");
sb.append("" + num);
}
printBanner(label);
System.out.printf("{ %s }\n", sb);
}
public static void printIntArray(int [] intArray, String label) {
StringBuffer sb = new StringBuffer();
for (int i: intArray) {
if (sb.length() > 0)
sb.append(", ");
sb.append("" + i);
}
printBanner(label);
System.out.printf("{ %s }\n", sb);
}
public static void printStringArray(String [] strArray, String label) {
StringBuffer sb = new StringBuffer();
for (String str: strArray) {
if (sb.length() > 0)
sb.append(", ");
sb.append("\n\"" + str.trim() + "\"");
}
printBanner(label);
System.out.printf("[ %s \n]", sb);
}
public static int getMinInteger(int [] intArray) {
int minInteger = intArray[0];
for (int i: intArray) {
if (i < minInteger)
minInteger = i;
}
return minInteger;
}
public static void convertIntegers(int [] intArray, int minInteger) {
for (int i = 0; i < intArray.length; i++) {
intArray[i] += minInteger;
}
}
public static int getMaxNumberInPositiveArray(int [] intArray) {
int maxNumber = intArray[0];
for (int num: intArray) {
if (maxNumber < num)
maxNumber = num;
}
return maxNumber;
}
public static void radixSortForStringByIndexCount(String [] original, String [] sorted, int index) {
int [] buckets = new int[256];
Arrays.fill(buckets, 0);
for (int i = 0; i < original.length; i++) {
buckets[(int)original[i].charAt(index)]++;
}
for (int i = 1; i < buckets.length; i++) {
buckets[i] += buckets[i-1];
}
for (int i = original.length-1 ; i >= 0; i--) {
sorted[--buckets[(int)original[i].charAt(index)]] = original[i];
}
}
public static void radixSortForStringByIndex(String [] original, String [] sorted, int maxStringLength) {
for (int index = maxStringLength-1; index >= 0; index--) {
radixSortForStringByIndexCount(original, sorted, index);
for (int i = 0; i < original.length; i++) {
original[i] = sorted[i];
}
}
}
public static int getMaxStringLength(String [] original) {
int maxStringLength = 0;
for (String str: original) {
if (str.length() > maxStringLength)
maxStringLength = str.length();
}
return maxStringLength;
}
public static void convertStrings(String [] original, int maxStringLength) {
for (int i = 0; i < original.length; i++) {
while (original[i].length() < maxStringLength) {
original[i] += " ";
}
}
}
public static String [] radixSortForStrings(String [] original) {
String [] sorted = new String[original.length];
int maxStringLength = getMaxStringLength(original);
convertStrings(original, maxStringLength);
radixSortForStringByIndex(original, sorted, maxStringLength);
return sorted;
}
public static int getMaxDecimalPlaces(float [] original) {
int maxDecimalPlaces = 0;
for (int i = 0; i < original.length; i++) {
String floatAsString = Float.toString(original[i]);
int index = floatAsString.indexOf('.');
if (index >= 0) {
if (floatAsString.substring(index+1).length() > maxDecimalPlaces)
maxDecimalPlaces = floatAsString.substring(index+1).length();
}
System.out.printf("original %f str %s index %d\n", original[i], floatAsString, index);
}
return maxDecimalPlaces;
}
public static float [] radixSortForFloats(float [] original) {
int [] originalAsInts = new int[original.length];
for (int i = 0; i < original.length; i++) {
originalAsInts[i] = (int)(original[i]*1000);
}
int [] sortedInts = radixSortForIntegers(originalAsInts);
float [] sortedFloats = new float[sortedInts.length];
for (int i = 0; i < original.length; i++) {
sortedFloats[i] = (float)(sortedInts[i] / 1000.0);
}
return sortedFloats;
}
public static int [] radixSortForIntegers(int [] original) {
int [] sorted = new int[original.length];
int minInteger = getMinInteger(original);
if (minInteger < 0) {
convertIntegers(original, minInteger*-1);
}
int maxNumber = getMaxNumberInPositiveArray(original);
radixSortForIntegersByPlace(original, sorted, maxNumber);
if (minInteger < 0) {
convertIntegers(sorted, minInteger);
}
return sorted;
}
public static void testIntegers() {
int [] original = getIntArray();
System.out.println();
printIntArray(original, "Original Integer Array");
int [] sorted = radixSortForIntegers(original);
printIntArray(sorted, "Sorted Integer Array");
}
public static void testFloats() {
float [] original = getFloatArray();
System.out.println();
printFloatArray(original, "Original Float Array");
float [] sorted = radixSortForFloats(original);
printFloatArray(sorted, "Sorted Float Array");
}
public static void testStrings() {
String [] original = getStringArray();
System.out.println();
printStringArray(original, "Original String Array");
String [] sorted = radixSortForStrings(original);
printStringArray(sorted, "Sorted String Array");
}
public static void main(String [] args) {
testIntegers();
testStrings();
testFloats();
}
}
7.2.2 Output
**************************************************************************************************************
Original Integer Array
--------------------------------------------------------------------------------------------------------------
{ -342, 1787, 1270, 993, 905, -1917, 1728, -692, -839, -1932 }
**************************************************************************************************************
Sorted Integer Array
--------------------------------------------------------------------------------------------------------------
{ -1932, -1917, -839, -692, -342, 905, 993, 1270, 1728, 1787 }
**************************************************************************************************************
Original String Array
--------------------------------------------------------------------------------------------------------------
[
"xD5JbrXP2Fo",
"Ym",
"dSlVimld",
"q",
"Z",
"YpSe5XfxE",
"2o7zi5CoSKHY",
"T4",
"r",
"GC8YS7H5"
]**************************************************************************************************************
Sorted String Array
--------------------------------------------------------------------------------------------------------------
[
"2o7zi5CoSKHY",
"GC8YS7H5",
"T4",
"Ym",
"YpSe5XfxE",
"Z",
"dSlVimld",
"q",
"r",
"xD5JbrXP2Fo"
]
**************************************************************************************************************
Original Float Array
--------------------------------------------------------------------------------------------------------------
{ 97459.1, 1515.29, 142789.4, -18210.49, -869.56, -5850.58, -42621.0, -16818.72, -73922.3, 10511.13 }
**************************************************************************************************************
Sorted Float Array
--------------------------------------------------------------------------------------------------------------
{ -73922.3, -42621.0, -18210.49, -16818.72, -5850.58, -869.56, 1515.29, 10511.13, 97459.1, 142789.4 }
8. Summary
In computing, there are often trade-offs that are made in order to accomplish the end goal. With Radix Sort, extra memory may be needed to create a result array to store the sorted elements. Some sorts with exponential time complexities do not require this extra memory because they sort the elements by swapping them.
9. Download the Source Code
You can download the full source code of this example here: Radix Sort in Java
