Radix Sorting and an Array of Strings

[ThisIsMeOrIsIt]

Hi all -

I need to write a program that reads in an array of strings from a file and uses a radixSort method to sort and print the array based on what characters they are composed of. The implementation should be able to handle strings of characters. The characters are from the following character set {!, (, ), ., <, >, ?, A, B, …, Z, [, ], a, b, …, z, {, } }.

The first line in the file is how many differnet elements are there, and the rest of the file are the strings to be read in.
With my program I am able to read a file and print the array as it is standard, but I can't figure out how to use radix sorting with strings and queues. Right now I am getting an EmptyQueueException when I try to run..my code so far is thus:

package programFive;

import queuepackage.*;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class RadixSort {

    public static void main(String[] args) throws FileNotFoundException{

        File inputFile = new File("testinput.txt");
        Scanner sc = new Scanner(inputFile);
        int arraySize = sc.nextInt();
        String[] unsortedArray = new String[arraySize];
        int n = unsortedArray.length;
        int d;

        for(int i = 0; i < unsortedArray.length; i++){
            String arrayInput = sc.next();
            unsortedArray[i] = new String(arrayInput);
        }

        String temp = unsortedArray[0];
        for(int j = 1; j < n; j++){
            if(unsortedArray[j].compareTo(temp) > 0){
                temp = unsortedArray[j];
            }
        }

        d = temp.length();


        printArray(unsortedArray);
        radixSort(unsortedArray, n, d);
        printArray(unsortedArray);



        sc.close();

    }

    public static void printArray(String[] unsortedArray){
        for(int i = 0; i < unsortedArray.length; i++){

            if (i < unsortedArray.length - 1)
                System.out.print(unsortedArray[i] + ",");
            else
                System.out.print(unsortedArray[i]);
        }
    }

    public static void radixSort(String[] unsortedArray, int n, int d){
        Queue[] queue = new Queue[n];
        for(int k = 0; k < n; k++){
            queue[k] = new Queue();
        }
        for(int i = d - 1; i >= 0; i--){
            for(int j = 0; j < n; j++){
            }
        }
        for(int index = 0; index < n; index++){
            for(int i = d - 1; i < 0; i++){
            char digit = (unsortedArray[index].charAt(i));
            int dig = Integer.parseInt(String.valueOf(digit));

            queue[dig].enqueue(unsortedArray[index]);
            }
        }
        for(int p = 0; p < n; p++){
            unsortedArray[p] = (queue[p].dequeue()).toString(); 
            }

        int item = 0; 
        for(int queueNum = 0; queueNum < n; queueNum++){
            while(!unsortedArray[queueNum].isEmpty()){

            }

        }
    }

}

[Taywin]

1)Where is the idea about using Queue coming from? Why do you think you need a queue for the sort?
2)Have you read and compared your implementation with this WikiPedia for the algorithm? Look closely at the C-language implementation. It should be the easiest one to follow. Ignore the C-syntax but you should be able to see how the flow of the inside process.
3)Is the passing in array modified after calling the sort method?

PS: Your way of comparing string is correct (use compareTo()).

[ThisIsMeOrIsIt]

1) We have to use Queues as part of the guidelines of the assignment.
2) I will take a look.
3) I'm not sure I understand the question, but I think after the sort method is called and runs through there shouldnt be any further modifications to the array.

[ThisIsMeOrIsIt]

I get using radix sort with integers a lot more than I understand using it with queues and strings. I just can't really figure out where to go from here.

[Taywin]

Ah I see. OK, do you know about ASCII character number? What you need to do is to deal with each digit as a number. When you deal with integer, you are dealing with each digit which is a character between 0 and 9. That's why you can use a bucket (queue) size of 10 to hold each number. In case of String you are dealing, you will need a little tweak by implementing your customized bucket queue.

A simple way but not very efficient is to create a bucket size of 256 (for each character ASCII value). Then you will use the ASCII values as indices in the buckets. Anything that is not in your character list, ignore those buckets.

/*
In integer way, you associate buckets with each integer digit.
buckets size is 10
digit 0 is buckets[0]
digit 1 is buckets[1]
...

In string way, you associate buckets with each ASCII character value.
Your valid character set
  { !, (, ), ., <, >, ?, A, B, …, Z, [, ], a, b, …, z, {, } }
bucket size is 256
char ! has ASCII char value 33, use buckets[33]
...
char A has ASCII char value 65, use buckets[65]
...
*/

[ThisIsMeOrIsIt]

This might be a shot in the dark, but is this kind of on the right track? I don't understand how I would write the program to set up different ASCII character buckets for each different character. Reading in 256 for bucketSize...

public static void radixSort(String[] unsortedArray, int bucketSize){
    int[] bucket = new int[bucketSize];

    for(int i = 0; i < bucket.length; i++){
        bucket[i] = 0;
        }

So if a sample input is as follows, where 5 is the number of the elements in the array.

5
AAAAA
z!<>!
BbaDd
OoOoo
p[>!!

How would I go about this...? Any tips are greatly appreciated.

[ThisIsMeOrIsIt]

Would I need to write many lines of code? For example:

if( charAt(i) == A){
    queueArray[i] = bucket[65];
    }

if(charAt(i) == !){
    queueArray[i] = bucket[33];
    }

etc etc

[Taywin]

The pass would be somewhat below (the number is the index used in your queue). The example is not that clear because they don't really have many duplicates to be groupped together. If there is no number, the queue at that index is not being used.

/*
 AAAAA, z!<>!, BbaDd, OoOoo, p[>!!
 pass: 1 from least significant position (last position)
 33 = z!<>!, p[>!!
 65 = AAAAA
 100 = BbaDd
 111 = OoOoo
 Result: z!<>!, p[>!!, AAAAA, BbaDd, OoOoo

 pass: 2 (character used from the list -- >, !, A, D, o)
 33 = p[>!!
 62 = z!<>!
 65 = AAAAA
 68 = BbaDd
 111 = OoOoo
 Result: p[>!!, z!<>!, AAAAA, BbaDd, OoOoo

 pass: 3 (character used from the list -- >, <, A, a, O)
 60 = z!<>!
 62 = p[>!!
 65 = AAAAA
 79 = OoOoo
 97 = BbaDd
 Result: z!<>!, p[>!!, AAAAA, OoOoo, BbaDd

 pass: 4 (character used from the list -- !, [, A, o, b)
 33 = z!<>!
 65 = AAAAA
 91 = p[>!!
 98 = BbaDd
 111 = OoOoo
 Result: z!<>!, AAAAA, p[>!!, BbaDd, OoOoo

 pass: 5 (character used from the list -- z, A, p, B, O)
 65 = AAAAA
 100 = BbaDd
 111 = OoOoo
 112 = p[>!!
 122 = z!<>!
 Result: AAAAA, BbaDd, OoOoo, p[>!!, z!<>!
*/

[Taywin]

One more... The bucket is still a list of queue.

Queue[] buckets;
int pos = maximum_string_length_in_the_unsorted_array - 1
for (int i=0; i<unsortedarray.length; i++) {
  buckets = new Queue[256];  // for each ASCII character value
  // then don't forget to initialize bucket queues
  ...
  char ch = unsortedarray[i].charAt(pos);
  // when the selected char is '!'
  int index = (int) ch;  // if you want to be explicit, convert the char to int first
  buckets[index] = unsortedarray[i];
  ...
  ...  // don't forget to move the "pos" value
}

[ThisIsMeOrIsIt]

I understand the logic of the passes, but I can't seem to figure it out in code. I have been looking at the Example in C that is on the Wikipedia page, and this is what I kind of have. Radix sorting makes so much more sense with intergers than Strings. I know I need a compareTo and a charAt method somewhere in the code..

public static void radixSort(String[] unsortedArray, int n){
int i;
int[] b = b[n];
int sortedArray = unsortedArray[0];
int exp = 1;
for(i = 0; i < n; i++){
    if(unsortedArray[i] > sortedArray){
        sortedArray = unsortedArray[i];
    }

    while(sortedArray / exp > 0){
        int bucket[256] = {0};
        for(i = 0; i < n; i++){
            bucket[unsortedArray[i] / exp % 256]++;}
        for(i = 1; i < 256; i++){
            bucket[i] += bucket[i - 1];}
        for(i = n - 1; i = 0; i--){
            b[--bucket[unsortedArray[i] / exp % 256]] = unsortedArray[i];}
        for(i = 0; i < n;i < n; i++){
            unsortedArray[i] = b[i];}

[Taywin]

I'm sorry for misleading you with the example in C. It is for integer only. What you need to do is a little bit different. Below is a pseudo code for the string sort. However, this works only with an array of string with the same length (i.e. ["abc", "cde", "efa", ...] but not ["abc", "cdef", "ab", ...]).

for each pos value from (maximum_string_length_in_an_unsorted_array-1) to 0
  queueArr <- new queue array size of 256
  for each index in the queueArr
    initial queueArr[index]
  end for
  for each index in unsorted_array  // sorting by position
    ch <- character at pos of the unsorted_array[index]
    enqueue queueArr[ASCII value of ch] with unsorted_array[index]
  end for
  dataIdx <- 0
  for each queueIndex from 0 up to 255  // regroup them
    while queueArr[queueIndex] is not empty
      unsorted_array[dataIdx] <- dequeue queueArr[queueIndex]
      increment dataIdx by 1
    end while
  end for
end for

If you want to be able to sort string with different length, you will have to find and deal with the maximum length of string in the array before you sort them.

[ThisIsMeOrIsIt]

I think I may have it, but I am running into an issue. I am getting an error saying that the dequeue(Queue) method is not defeind for type String. It is on the second line from the bottom.

public static void radixSort(String[] unsortedArray, int length){

        for(int i = 0; i < length; i++){
            Queue[] queueArray = new Queue[256];

            for(int index = 0; index < queueArray.length; index++){
                queueArray[index] = new Queue();
            }

            for(int index = 0; index < unsortedArray.length; index++){
                char digit = (unsortedArray[index].charAt(index));
                int dig = Integer.parseInt(String.valueOf(digit));

                queueArray[dig].enqueue(unsortedArray[index]);
                }

            int dataIdx = 0;
            for(int queueIndex = 0; queueIndex <= 255; queueIndex++){
                while(!queueArray[queueIndex].isEmpty()){
                    unsortedArray[dataIdx].dequeue(queueArray[queueIndex]);
                    dataIdx++;

[ThisIsMeOrIsIt]

I figured it out. Thanks so much for your help Taywin, you can't imagine how much I appreciate it.

[fattaco]

Hi,
can you post the working code for this project? i have a similar problem to solve.

Thanks