ISC Practicals and Theory - Word Length Sort (OOP)

This program reads a sentence and prints its words in ascending order of length, each with its length. It is written as a class with a parameterised constructor and small methods that each do one job: countWords(), extract(), 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 in which words of equal length keep their original order.

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. The length of a word is given by length().

Sorting by length in ascending order puts the shortest word first. The sort is stable: two words of equal length stay in the order typed. Bubble sort is stable when it swaps neighbours only if the first is strictly longer (>); selection sort as usually written is not stable.

Example: go to bed a. gives a, go, to, bed (lengths 1, 2, 2, 3); go stays before to.

Algorithm

1. main reads the line with Scanner and creates the object with the parameterised constructor WordLength(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 w[j].length() > w[j + 1].length() it calls swap(j, j + 1). Equal lengths are not swapped.
   • swap(x, y) interchanges w[x] and w[y] using a temporary variable t.
7. display() prints the heading Word : Length and then each word with its length, one per line.

Program

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

import java.util.Scanner;

/* Class WordLength stores a sentence, extracts its words without split() or
   StringTokenizer and arranges them by length (shortest first) using
   bubble sort. Every method does one job. */
public class WordLength
{
    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. */
    WordLength(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 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 by length, shortest word first. A swap is made only when
       the first word is STRICTLY longer (>), so words of equal length keep
       their original order. */
    void sortWords()
    {
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (w[j].length() > w[j + 1].length())   // out of order
                    swap(j, j + 1);
            }
        }
    }

    /* Prints each word with its length, one word per line */
    void display()
    {
        System.out.println("Word : Length");
        for (int i = 0; i < n; i++)
            System.out.println(w[i] + " : " + w[i].length());
    }

    /* 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
        WordLength ob = new WordLength(line);   // object of class WordLength
        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: go to bed a.
Word : Length
a : 1
go : 2
to : 2
bed : 3

Enter a sentence: the quick brown fox jumps over the lazy dog.
Word : Length
the : 3
fox : 3
the : 3
dog : 3
over : 4
lazy : 4
quick : 5
brown : 5
jumps : 5

Enter a sentence:   Go   to   a  big  Sea  and   it !
Word : Length
a : 1
Go : 2
to : 2
it : 2
big : 3
Sea : 3
and : 3

Enter a sentence: Hello?
Word : Length
Hello : 5

Enter a sentence: Welcome to Prashnika
INVALID INPUT

Enter a sentence: .
INVALID INPUT

Dry run

Input go to bed a. The sentence has 12 characters, so len = 11. Characters 0 and 1 are go, 2 is a space, 3 and 4 are to, 5 is a space, 6 to 8 are bed, 9 is a space, 10 is a and 11 is the terminator ..

Counting and extracting. countWords() returns 4, so n = 4. Then extract() runs:

Sorting. w = [go, to, bed, a] with lengths 2, 2, 3, 1. n = 4, so there are three passes.

The program prints a : 1, go : 2, to : 2, bed : 3 under the heading, the same as the real run above.

Variations

1. Alphabetical order "Arrange the words of a sentence in alphabetical order."
2. Descending length "Arrange the words of a sentence in descending order of their length."
3. Longest and shortest "Print the longest word and the shortest word of a sentence."