ISC Practicals and Theory - Word Length Sort

This program reads a sentence, separates it into words and prints the words in ascending order of their length, each with its length. 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. Words of equal length stay in the order in which they were typed. Everything is written in the main method.

Definition

A sentence here is a line of text 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 the String method length().

Sorting by length in ascending order puts the shortest word first. A sort is stable when two items with equal keys keep their original relative order. Bubble sort is stable if it swaps two neighbours only when the first is strictly longer (>), never when they are equal. Selection sort (as usually written) is not stable, which is why bubble sort is used here.

Example: go to bed a. has the words go, to, bed, a with lengths 2, 2, 3, 1. Sorted by length they become a, go, to, bed. go stays before to because both have length 2.

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 the lengths of w[j] and w[j + 1] and swap them only if the first is strictly longer (>). Words of equal length are never interchanged, so they keep their original order.
7. Print the heading Word : Length and then each word with its length.

Program

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

import java.util.Scanner;

/* Program WordLength reads a sentence, separates it into words without split() or
   StringTokenizer and arranges them by length (shortest first) using
   bubble sort. Words of equal length stay in their original order. */
public class WordLength
{
    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: neighbouring words are swapped only when the first is STRICTLY longer (>),
        // so words of equal length are never interchanged and keep their original order
        for (int p = 0; p < n - 1; p++)
        {
            for (int j = 0; j < n - 1 - p; j++)
            {
                if (w[j].length() > w[j + 1].length())   // out of order
                {
                    String t = w[j];                // swap using a temporary variable
                    w[j] = w[j + 1];
                    w[j + 1] = t;
                }
            }
        }
        System.out.println("Word : Length");
        for (int q = 0; q < n; q++)
            System.out.println(w[q] + " : " + w[q].length());
    }
}

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

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. The counting loop finds four words, so n = 4.

Now w = [go, to, bed, a] with lengths 2, 2, 3, 1.

Sorting. n = 4, so there are three passes.

The program prints the words in the order a, go, to, bed with the lengths 1, 2, 2, 3, the same as the real run above. go is still before to.

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."
4. Insertion sort "Arrange the words of a sentence by length using insertion sort."