Programming Assignment 3

Linear Stable Sorting

Data Structures & Algorithms Fall 2009


Due Date

This assignment is due by 11:30 p.m. on Tuesday, 24 November.

See the assignment turn-in page (last modified on 22 September 2009) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 3 is Friday, 27 November at 11:30 p.m.. It is not possible to turn-in Assignment 3 after the absolute deadline.

The Problem

Write a program that reads from std-in zero or more pairs of strings. In each pair the first string is a person's name and the second string is the person's favorite fruit. The pairs read will be in ascending alphabetical order by name. Your program should write to std-out the input pairs in ascending alphabetical order by fruit. Within the group of pairs having the same fruit, the pairs should be output in ascending order by name (that is, the same order appearing on input). Your program should execute in O(n) time, where n is the number of pairs read.

Input

Input is read from std-in and is a sequence of n ≥ 0 string pairs. Each string is a single word (that is, a word with no internal space characters); case is ignored. Adjacent strings are separated by one or more space characters. Consecutive string pairs are given in ascending alphabetical order on the first string.

Example input:

Albert pear
Barbara apple
Charlie watermelon
Donna pear
Edgar apple

The total number of fruit in any input list is unknown, but all fruit listed are unique with respect to their starting letter. For example, before an input list is read, it is unknown whether or not the list contains a fruit starting with ‘a’. However, if there is a fruit starting with ‘a’, it is the only fruit on the list that does start with ‘a’.

You may assume that any input read is formatted as described above.

Output

All pairs read should be written to std-out; adjacent strings should be separated by at least one space character. Pairs should be output in ascending alphabetic order by fruit; within a group of pairs having the same fruit, pairs should be written in ascending alphabetic order by name.

Example output:

Barbara apple
Edgar apple
Albert pear
Donna pear
Charlie watermelon

Implementing

Your code should be implemented in a package called assignment . You should build any data structures you need; relying on Java library data structures is not allowed.


This page last modified on 26 October 2009.