JAVA Program : Write a version of Radix Sort for Strings to sort an array of Str

Question

JAVA Program :

Write a version of Radix Sort for Strings to sort an array of String objects.

. The String object will only contain ASCII characters,

. The maximum size (length) of any String object is 20

. Use the charAt() method of the String class.

. Run the algorithm on a set of at least 10 strings and have it print the results.

. Note that it is not a comparison sort – you don’t compare two strings. It involves looking at subcomponents of the items being sorted. In the case of strings, these subcomponents are characters

Explanation / Answer

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Vamsi
*/
public class RadixSort {
  
  
//sorting method
  
public static void radixSort(List<String> list, int max) {
if (list.size() <= 1) {
return;
}

List<String>[] buckets = new List[27];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new LinkedList<>();
}
int maxLength = -1;
int secondmaxLength = 0;
for (String s : list) {
int length = s.length();
if (length >= maxLength) {
secondmaxLength = maxLength;
maxLength = length;
} else if (secondmaxLength < length) {
secondmaxLength = length;
}
}

if (maxLength > max) {
throw new IllegalArgumentException("String in tooo long");
}

for (int i = secondmaxLength == maxLength ? secondmaxLength-1 : secondmaxLength; i >= 0; i--) {
for (String word : list) {
int index = (word.length() <= i) ? 0 : word.charAt(i) - ('a' - 1);
buckets[index].add(word);
}

list.clear();

for (List<String> lst : buckets) {
if (lst != null) {
list.addAll(lst);
lst.clear();
}
}
}
}

//testing method..
public static void main(String argv[])
{
int length=20;//strings length max
//array of strings..
List<String> l=new LinkedList<>();
  
Scanner sc = new Scanner(System.in);
System.out.println("Enter 10 strings(max length 20):");
int i=0;
while(i<10)
{
  
String s = sc.next();
l.add(s);
i++;
}
//calling radix sort..
radixSort(l,length);
  
//sorted list..
i=0;
System.out.println("Sorted list: ");
while(i<10)
{
System.out.println(l.get(i));
i++;
  
}
}
  
}

output:

run:
Enter 10 strings(max length 20):
tre
a
bs
hrt
fd
srg
jyd
fg
t
h
Sorted list:

a
bs
fd
fg
h
hrt
jyd
srg
t
tre
BUILD SUCCESSFUL (total time: 1 minute 13 seconds)
t

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.