In Java. modify the radix sort method to allow strings of various lengths to be

Question

In Java. modify the radix sort method to allow strings of various lengths to be properly sorted WITHOUT any additional data structures used to store data

i.e. array.sort or Compareto()

For example:

abdef

abd

abde

Would be sorted to..

abd

abde

abdef

Method:

public static void radixSortStrings(String[] arr, int strLen)

{

//number of buckets = 256 (characters in the character set)

int buckets = 256;

//if you were doing a case insensitive sort, and you knew everything was single words, you could use 26 as your size

//Buckets need to be lists instead of counters

ArrayList<String>[] bucket = new ArrayList[buckets];

//create array of lists and initialize each object

for(int i = 0; i < buckets; i++)

{

bucket[i] = new ArrayList<>();

}

//pointer for position in original list

int index = 0;

//loop from end of string to beginning

for(int i = strLen-1; i >= 0; i--)

{

index = 0;

//loop through each string

for(int j = 0; j < arr.length; j++)

{

//add to appropriate bucket

bucket[(int)arr[j].charAt(i)].add(arr[j]);

}

System.out.println("Sorted on character "+i);

//loop through buckets

for(int j = 0; j < bucket.length; j++)

{

if(bucket[j].size() > 0)

System.out.println(j+":"+bucket[j].toString());

//add each string back to original array in new order

for(String s : bucket[j])

{

arr[index] = s;

index++;

}

//clear the bucket

bucket[j].clear();

}

}

}

:

Explanation / Answer

public static void radixSortStrings( String [ ] arr, int strLen )
{
final int BUCKETS = 256;

ArrayList<String> [ ] buckets = new ArrayList[ BUCKETS ];
  
for( int i = 0; i < BUCKETS; i++ )
buckets[ i ] = new ArrayList<>( );
  
for( int pos = strLen - 1; pos >= 0; pos-- )
{
for( String s : arr )
buckets[ s.charAt( pos ) ].add( s );
  
int idx = 0;
for( ArrayList<String> thisBucket : buckets )
{
for( String s : thisBucket )
arr[ idx++ ] = s;
  
thisBucket.clear( );
}
}
}

public static void countingRadixSort( String [ ] arr, int strLen )
{
final int BUCKETS = 256;
  
int N = arr.length;
String [ ] buffer = new String[ N ];

String [ ] in = arr;
String [ ] out = buffer;
  
for( int pos = strLen - 1; pos >= 0; pos-- )
{
int[ ] count = new int [ BUCKETS + 1 ];
  
for( int i = 0; i < N; i++ )
count[ in[ i ].charAt( pos ) + 1 ]++;

for( int b = 1; b <= BUCKETS; b++ )
count[ b ] += count[ b - 1 ];

for( int i = 0; i < N; i++ )
out[ count[ in[ i ].charAt( pos ) ]++ ] = in[ i ];
  
// swap in and out roles
String [ ] tmp = in;
in = out;
out = tmp;
}
  
// if odd number of passes, in is buffer, out is arr; so copy back
if( strLen % 2 == 1 )
for( int i = 0; i < arr.length; i++ )
out[ i ] = in[ i ];
}
  

public static void radixSort( String [ ] arr, int maxLen )
{
final int BUCKETS = 256;

ArrayList<String> [ ] wordsByLength = new ArrayList[ maxLen + 1 ];
ArrayList<String> [ ] buckets = new ArrayList[ BUCKETS ];
  
for( int i = 0; i < wordsByLength.length; i++ )
wordsByLength[ i ] = new ArrayList<>( );
  
for( int i = 0; i < BUCKETS; i++ )
buckets[ i ] = new ArrayList<>( );
  
for( String s : arr )
wordsByLength[ s.length( ) ].add( s );

int idx = 0;
for( ArrayList<String> wordList : wordsByLength )
for( String s : wordList )
arr[ idx++ ] = s;
  
int startingIndex = arr.length;
for( int pos = maxLen - 1; pos >= 0; pos-- )
{
startingIndex -= wordsByLength[ pos + 1 ].size( );
  
for( int i = startingIndex; i < arr.length; i++ )
buckets[ arr[ i ].charAt( pos ) ].add( arr[ i ] );
  
idx = startingIndex;
for( ArrayList<String> thisBucket : buckets )
{
for( String s : thisBucket )
arr[ idx++ ] = s;
  
thisBucket.clear( );
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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