ISC Practicals and Theory - Alphabetical Word Sort

This program reads a sentence, separates it into words and prints the words in alphabetical (dictionary) order. The words are taken out of the sentence with charAt(), substring() and length() only, with no split() and no StringTokenizer, stored in a String array and arranged with a bubble sort written by hand. Everything is written in the main method.

Definition

A sentence here is a line of text that ends with one of the terminators ., ? or !. Its words are the groups of characters separated by one or more spaces; the terminator is not part of the last word. Alphabetical order (ascending) means the order of a dictionary: apple comes before banana, and fig before pear.

Words are compared with the String method compareToIgnoreCase(). For two words a and b, a.compareToIgnoreCase(b) returns a positive number if a comes after b, 0 if they are the same apart from case, and a negative number if a comes before b. Bubble sort swaps two neighbouring words when this value is greater than 0.

Why not compareTo()? compareTo() compares the character codes, and every capital letter has a smaller code than every small letter. So compareTo() would put Zebra before apple. compareToIgnoreCase() treats Zebra and zebra alike, so apple comes before Zebra, as in a dictionary. The words are printed with their original case.

Example: pear Apple fig. has the words pear, Apple, fig and sorts to Apple fig pear.

If two words are equal ignoring case (such as apple and Apple), the sort does not swap them, so they stay in the order typed.

Algorithm

1. Read the line into sent and remove the spaces at its two ends with trim().
2. The last character is the terminator. If the sentence is empty, or the terminator is not ., ? or !, print INVALID INPUT and stop.
3. Let len = sent.length() - 1, the length without the terminator. Count the words in n: scan i from 0 to len - 1; a space is skipped, and any other character starts a new word, so add 1 to n and move i to the end of the word.
4. If n is less than 1 or more than 50, print INVALID INPUT and stop.
5. Create the array w of size n and scan the sentence again. When a word starts, note start = i, move i to the end of the word and store sent.substring(start, i) in w[k], then increase k.
6. Arrange the words with a bubble sort: in each pass p, compare w[j] and w[j + 1] with compareToIgnoreCase() and swap them if the first is greater.
7. Print Sorted words: followed by the words of the array in order.

Program

The program in main first checks the sentence, then counts the words, stores them in the array w, sorts the array with a bubble sort and prints it.

import java.util.Scanner;

/* Program WordSort reads a sentence, separates it into words without using split() or
   StringTokenizer and arranges them in alphabetical (dictionary) order
   using bubble sort. */
public class WordSort
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String sent = sc.nextLine().trim();         // trim() removes spaces at the two ends of the line
        char last = ' ';                            // the terminator
        if (sent.length() > 0)
            last = sent.charAt(sent.length() - 1);
        if (last != '.' && last != '?' && last != '!')
        {
            System.out.println("INVALID INPUT");
            return;
        }
        int len = sent.length() - 1;                // length without the terminator
        int i = 0, n = 0;                           // n counts the words
        while (i < len)
        {
            if (sent.charAt(i) == ' ')              // extra space: skip it
                i++;
            else
            {
                n++;                                // a new word starts here
                while (i < len && sent.charAt(i) != ' ')
                    i++;                            // move to the end of the word
            }
        }
        if (n < 1 || n > 50)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        String w[] = new String[n];                 // array that stores the words
        i = 0;
        int k = 0;
        while (i < len)
        {
            if (sent.charAt(i) == ' ')
                i++;
            else
            {
                int start = i;                      // index where the word begins
                while (i < len && sent.charAt(i) != ' ')
                    i++;
                w[k] = sent.substring(start, i);    // word = start to i - 1
                k++;
            }
        }
        // bubble sort; compareToIgnoreCase() ignores the case of the letters,
        // so "apple" and "Banana" are compared as a and b and not by ASCII codes
        for (int p = 0; p < n - 1; p++)
        {
            for (int j = 0; j < n - 1 - p; j++)
            {
                if (w[j].compareToIgnoreCase(w[j + 1]) > 0)   // out of order
                {
                    String t = w[j];                // swap using a temporary variable
                    w[j] = w[j + 1];
                    w[j + 1] = t;
                }
            }
        }
        System.out.print("Sorted words:");
        for (int q = 0; q < n; q++)
            System.out.print(" " + w[q]);
        System.out.println();
    }
}

Variable description table

Sample input and output

Enter a sentence: pear Apple fig.
Sorted words: Apple fig pear

Enter a sentence:   Zebra   apple  Mango apple   banana !
Sorted words: apple apple banana Mango Zebra

Enter a sentence: Hello?
Sorted words: Hello

Enter a sentence: Welcome to Prashnika
INVALID INPUT

Dry run

Input pear Apple fig. The sentence has 15 characters, so len = 14. Characters 0 to 3 are pear, 4 is a space, 5 to 9 are Apple, 10 is a space, 11 to 13 are fig and 14 is the terminator ..

Counting and extracting. The counting loop finds three words, so n = 3.

Now w = [pear, Apple, fig] and k = 3.

Sorting. n = 3, so there are two passes.

The program prints Sorted words: Apple fig pear, the same as the real run above.

Variations

1. Length order "Arrange the words of a sentence in ascending order of their length."
2. Descending order "Sort the words of a sentence in descending alphabetical order."
3. Selection sort "Arrange the words of a sentence in alphabetical order using selection sort."
4. Words starting with a vowel "Count the words of a sentence that begin with a vowel."