ISC Practicals and Theory - Alphabetical Word Sort (OOP)

This program reads a sentence and prints its words in alphabetical (dictionary) order. It is written as a class with a parameterised constructor and small methods that each do one job: countWords(), extract(), compare(), swap() and sortWords(). The words are taken out with charAt(), substring() and length(), with no split() and no StringTokenizer, and sorted by a hand-written bubble sort.

Definition

A sentence is a line that ends with ., ? or !. Its words are the groups of characters separated by one or more spaces; the terminator is not part of the last word. In ascending alphabetical order apple comes before banana, and fig before pear.

Words are compared with the String method compareToIgnoreCase(), which returns a positive number if the first word comes after the second, 0 if they are equal ignoring case and a negative number if it comes before. compareTo() would put every capital letter before every small letter (Zebra before apple) because capital letters have smaller character codes, so the case-blind version is used and the words print in their original case.

Example: pear Apple fig. gives Apple fig pear. Words equal ignoring case are never swapped, so they stay in the order typed.

Algorithm

1. main reads the line with Scanner and creates the object with the parameterised constructor WordSort(line), which stores the trimmed line in sent.
2. isValid() checks that sent is not empty and ends with ., ? or !; otherwise main prints INVALID INPUT and stops.
3. countWords() returns the number of words, which main stores in n. It scans the characters before the terminator: a space is skipped, any other character starts a word (add 1 to count) and i moves to the end of that word.
4. If n is less than 1 or more than 50, main prints INVALID INPUT and stops.
5. extract() creates w with n places and scans the sentence again. For each word it stores sent.substring(start, i) in w[k].
6. sortWords() is a bubble sort. For i from 0 to n - 2 and j from 0 to n - 2 - i, if compare(w[j], w[j + 1]) > 0 it calls swap(j, j + 1).
   • compare(a, b) returns a.compareToIgnoreCase(b).
   • swap(x, y) interchanges w[x] and w[y] using a temporary variable t.
7. display() prints Sorted words: followed by each word, with a space before it.

Program

The constructor stores the sentence. isValid(), countWords() and extract() prepare the words, compare() and swap() are the two helpers of sortWords(), and display() prints. main reads the input, creates the object and calls the methods.

import java.util.Scanner;

/* Class WordSort stores a sentence, extracts its words without split() or
   StringTokenizer and arranges them in alphabetical (dictionary) order
   using bubble sort. Every method does one job. */
public class WordSort
{
    String sent;     // the sentence (trimmed, with its terminator)
    String w[];      // array that stores the words of the sentence
    int n;           // number of words in the sentence

    /* Parameterised constructor. Parameter s: the sentence typed by the user.
       trim() removes spaces at the two ends of the line. */
    WordSort(String s)
    {
        sent = s.trim();
        w = null;
        n = 0;
    }

    /* Returns true if the sentence is not empty and ends with '.', '?' or '!',
       otherwise false. */
    boolean isValid()
    {
        if (sent.length() == 0)
            return false;
        char last = sent.charAt(sent.length() - 1);   // the terminator
        return last == '.' || last == '?' || last == '!';
    }

    /* Counts the words of the sentence and returns the count.
       The last character (the terminator) is not examined. */
    int countWords()
    {
        int len = sent.length() - 1;   // length without the terminator
        int i = 0;
        int count = 0;                 // number of words found so far
        while (i < len)
        {
            if (sent.charAt(i) == ' ')     // extra space: skip it
                i++;
            else
            {
                count++;                   // a new word starts here
                while (i < len && sent.charAt(i) != ' ')
                    i++;                   // move to the end of the word
            }
        }
        return count;
    }

    /* Extracts the words one by one with substring() and stores them in w.
       Uses n, the number of words, to make the array. */
    void extract()
    {
        int len = sent.length() - 1;   // length without the terminator
        int i = 0, k = 0;
        w = new String[n];
        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++;
            }
        }
    }

    /* Parameters a and b: two words. Returns a negative number if a comes
       before b in the dictionary, 0 if they are equal and a positive number
       if a comes after b. The case of the letters is ignored. */
    int compare(String a, String b)
    {
        return a.compareToIgnoreCase(b);
    }

    /* Parameters x and y: positions in w. Interchanges the two words. */
    void swap(int x, int y)
    {
        String t = w[x];       // temporary variable
        w[x] = w[y];
        w[y] = t;
    }

    /* Bubble sort: arranges the words in ascending alphabetical order */
    void sortWords()
    {
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (compare(w[j], w[j + 1]) > 0)   // out of order
                    swap(j, j + 1);
            }
        }
    }

    /* Prints the sorted words on one line, separated by a space */
    void display()
    {
        System.out.print("Sorted words:");
        for (int i = 0; i < n; i++)
            System.out.print(" " + w[i]);
        System.out.println();
    }

    /* main reads the sentence, creates the object and calls the methods.
       The sentence must have at least 1 and at most 50 words, else
       INVALID INPUT is printed. */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a sentence: ");
        String line = sc.nextLine();          // sentence typed by the user
        WordSort ob = new WordSort(line);     // object of class WordSort
        if (!ob.isValid())
        {
            System.out.println("INVALID INPUT");
            return;
        }
        ob.n = ob.countWords();
        if (ob.n < 1 || ob.n > 50)
        {
            System.out.println("INVALID INPUT");
            return;
        }
        ob.extract();
        ob.sortWords();
        ob.display();
    }
}

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

Enter a sentence: .
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. countWords() returns 3, so n = 3. Then extract() runs:

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."