I was recently given the task to implement an LSD Radix Sort algorithm to sort a set of strings (a list of names, specifically). Being that there aren’t many examples of this online, I’ve decided to share this. Admittedly, this took me some time to figure out, but looking back, it’s really not too difficult. You may download the complete source to run yourself by clicking here.
Instructions
This assignment is to alphabetically sort n strings, each with maximum-length of k = 21 characters. (You may assume n ≤ 1000.) The algorithm to be used is LSD (Least-Significant-Digit-First) radixsort. The algorithm must run in O(n) time, where one character operation takes one unit of time. You must handle the strings on a character-by-character basis, one character at a time. (Each character operation takes O(1) time.) The strings consist of only upper-case letters A-Z, with no space. The strings need not be distinct. (For example, there may be several PATEL in a class list!). Each string has at most k characters. Shorter strings must be padded with blank characters (as they are read from a file) to reach the fixed length of k.
So, we need to open an input file, read each line char-by-char, and pad each string to the maximum number of characters (21; using blank spaces). Once this is done, we will sort the list (char-by-char) starting from the least significant digit (the last letter), moving inward, until we’ve sorted all of the strings in the list. Sounds easy enough, right? 
How does it work?
Using LSD Radix Sort, we are sorting a list of integers based on the last digit moving inward until you reach the first digit. To actually sort the elements, you must place them in a bucket (I used a linked list) according to that digit (ASCII). Eventually, when you reach the first digit for each integer in the list, they should fall into order according to the bucket. Confused yet?
Well, the algorithm can be described as follows:
- Take the least significant digit of the key.
- Group the key based on that digit while keeping the original order (stable sort).
- Repeat, using the next significant digit.
Sounds easy enough, but the second instruction is somewhat ambiguous, and we need to figure out a way to implement this idea.
Reading the Input File
This part of the code is really trivial, but we need to figure out how many names are in the list and then pad each name to the maximum number of characters so we can properly sort them. Here is the class I used for loading the input file, initializing the array of strings, and padding each string:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class LoadConfiguration {
private String fileName; // Configuration File Name
private String[] names; // Array of String Objects
private int numberOfNames; // Number of Names
protected static final int MAXLENGTH = 21; // Max length of any String
/**
* Default constructor
*/
public LoadConfiguration() {
this.fileName = "input.txt";
} // end default constructor
/**
* Overloaded constructor
* @param fileName
*/
public LoadConfiguration ( String fileName ) {
this.fileName = fileName;
} // end overloaded constructor
/**
* This method returns the String
* array of names.
*
* @return String[] names
*/
public String[] getNames() {
return names;
} // end method getNames
/**
* This method returns the number
* of names in the array.
*
* @return int
*/
public int getNumberOfNames() {
return numberOfNames;
} // end method getNumberOfNames
/**
* This method reads the input file
* and counts the number of lines.
*/
public void initialize() {
write("Using input file: " + fileName);
try {
BufferedReader br = new BufferedReader( new FileReader( fileName ) );
/**
* While the line is not null,
* keep reading the file.
*/
while ( ( br.readLine()) != null ) {
numberOfNames++;
}
names = new String[ numberOfNames ]; // Initialize array
} catch ( IOException e ) {
write("Error Reading File: " + e + "\n");
System.exit(0);
} // end try
} // end method initialize
/**
* This method reads the given
* file.
*/
public void readFile() {
write("-------------------------------------------------------");
write("Original Unsorted List:");
write("-------------------------------------------------------");
try {
String line; // String to store each line
BufferedReader br = new BufferedReader( new FileReader( fileName ) );
/**
* While the line is not null,
* keep reading the file.
*/
int i = 0;
while ( ( line = br.readLine()) != null ) {
/**
* While the string is less than the max
* length, add a space to the end of the
* string (padding it).
*/
while ( line.length() < MAXLENGTH ) {
line = line + " "; // Pad string
} // end while
names[i++] = line; // Add String to array
} // end while
/**
* Print the names in the
* array
*/
for ( int j = 0; j < names.length; j++ ) {
write( names[j] );
} // end for loop
write("");
} catch ( IOException e ) {
write("Error Reading File: " + e + "\n");
} // end try
} // end method readFile
/**
* This method writes to the Log file
* and to the system out.
*
* @param String message
*/
public void write( String message ) {
System.out.println( message );
} // end method write
} // end LoadConfiguration
Performing the LSD Radix Sort
Now that we’ve got our list of names (stored in an array), we need to write a class to load either a default or a specified input file, and sort the list of names. Because of the amount of comments I left in this file, I won’t say anymore. Here it is:
import java.util.LinkedList;
public class LSDRadixSort {
private static final int BUCKETSIZE = 256; // Bucket Size 256 (0-25 letters of alphabet)
private static final int MAXLENGTH = 21; // Maximum Length of any String
private static int NUMNAMES; // Number of names
/**
* Default Constructor
*/
public LSDRadixSort() {} // end default constructor
/**
* This method returns the last
* char in a given string, used
* for getting the bucket number.
*
* @param String s
* @return int c
*/
private static int getLastChar( String s ) {
int c = (int) s.charAt( s.length() -1 );
return c;
} // end method getLastChar
/**
* Main method
*
* @param args
*/
@SuppressWarnings("unchecked")
public static void main( String[] args ) {
new LSDRadixSort(); // New Radix Sort
write("\nDefault Usage: java LSDRadixSort");
write("\n\nTo load your own configuration file:");
write("----------------------------------------------------");
write("java LSDRadixSort pathToYourConfigFile\n\n");
LoadConfiguration lc = null; // Initialize LoadConfiguration (input file reader)
/**
* Load the default config file
*/
if ( args.length < 1 ) {
write("Reading default input file...");
lc = new LoadConfiguration(); // Use the default input file
}
/**
* Load a given config file
*/
else {
write("Reading given input file... (overriding default).");
lc = new LoadConfiguration( args[0] ); // User is using their own input file
}
/**
* Make sure config file is not null
*/
if ( lc != null ) {
lc.initialize(); // Initialize the array from the input file
lc.readFile(); // Read the input file and pad its strings
NUMNAMES = lc.getNumberOfNames(); // Get the number of names
System.out.println(); // Print a blank line for the output
} else {
write("Error: Could not read config file.");
}
LinkedList[] bucket = new LinkedList[ BUCKETSIZE ]; // New array of linked lists
/**
* Initialize Buckets
*/
for ( int i = 0; i < BUCKETSIZE; i++ ) {
bucket[i] = new LinkedList<String>(); // New linked list for each bucket
}
/**
* Add names to respective bucket
* according to last char
*/
for ( int i = 0; i < NUMNAMES; i++ ) {
int destBinNumber = getLastChar( lc.getNames()[i] ); // Get the bin number according to last char
bucket[destBinNumber].add( lc.getNames()[i] ); // Add the name to the bin number
}
/**
* Repeat the process for each letter
* of each string from each bucket
*/
write("\n\n-------------------------------------------------------");
write("Performing LSD Radix Sort:");
write("-------------------------------------------------------");
for ( int i = MAXLENGTH-1; i >= 0; i-- ) { // -1 since we already have our initial array
// Check all elements of array 0-255
for ( int j = 0; j < BUCKETSIZE; j++ ) {
if ( !bucket[j].isEmpty() ){ // While bucket is not empty, perform LSD Radix Sort
String[] element = new String[ bucket[j].size() ]; // Array to store elements from bucket
for ( int x = 0; x < element.length; x++ ) { // For the # of elements, perform LSD Radix Sort
element[x] = (String) bucket[j].poll(); // Remove element from bucket, add to array
int destBinNumber = element[x].charAt(i); // Get destination bin number for this element
bucket[destBinNumber].add(element[x]); // Add element to its [new] bucket
write( "i:\t" + i + "\tj:\t" + j + "\tElement:\t" + element[x] + "Char:\t[" + element[x].charAt(i) + "]\t" +
"Bucket:\t" + destBinNumber);
} // end for loop
} // end if
} // end for loop
} // end for loop
/**
* Print out bucket list of names
*/
write("\n\n-------------------------------------------------------");
write("Elements in Appropriate Buckets (FINAL):");
write("-------------------------------------------------------");
for ( int i = 0; i < BUCKETSIZE; i++ ) {
System.out.println( i + ". " + bucket[i] );
Log.write( i + ". " + bucket[i] );
} // end for loop
/**
* Print out final sorted list
*/
write("\n\n-------------------------------------------------------");
write("Final Sorted List:");
write("-------------------------------------------------------");
for ( int i = 0; i < BUCKETSIZE; i++ ) {
if ( !bucket[i].isEmpty() ) {
String[] element = new String[ bucket[i].size() ]; // Array to store elements from bucket
for ( int x = 0; x < element.length; x++ ) {
element[x] = (String) bucket[i].poll(); // Remove element from bucket, add to array
write( element[x] ); // Print
} // end for loop
} // end if
} // end for loop
} // end main method
/**
* This method writes to the Log
* file and to the system out.
*
* @param String message
*/
public static void write( String message ) {
System.out.println( message );
} // end method write
} // end class LSDRadixSort
Sample Input
This file is saved as input.txt. As you can see, it is a standard text file containing last names in all caps, and each new name is started on a new line.
RODRIGUEZ
BLACK
SMITH
WHITE
CACERAS
SAMSUNG
FAUST
REISS
EISENMANN
MILLER
PARK
DALE
DEAN
OLPHERT
PHELEPS
SMOTHERS
Sample Output
This file is saved as output.txt. Now we can see that the names have been sorted in alphabetical order using the LSD Radix Sort algorithm above. Note that the output is actually much larger and in greater detail, but I’ve simplified it for this post.
BLACK
CACERAS
DALE
DEAN
EISENMANN
FAUST
MILLER
OLPHERT
PARK
PHELEPS
REISS
RODRIGUEZ
SAMSUNG
SMITH
SMOTHERS
WHITE
Conclusion
As you can see, with some while loops, for loops, arrays, and Java’s LinkedList class, we can [somewhat] easily perform the LSD Radix Sort on a set of strings. Normally this sorting algorithm is used to sort integers, but since the characters of strings represent numbers in ASCII, we have no problems sorting names or other strings, as well.
Tags: lsd, radix sort