C Alphabetic Sort

Description

Sorting, or arranging objects in a prescribed order, is one of the most fundamental tasks in computer programming. In this problem, you are required to write a C program, called alphabetic_sort.c, that reads a sequence of words from an input file and sorts these words in ascending alphabetical order.

Numerous efficient algorithms for sorting, such as merge sort, tree sort, and heapsort, are well known. You are welcome to use any of these algorithms. You are also welcome to use the inefficient, but simple, algorithm described in what follows. Let S = {S1, S2, . . .,Sn} be a set of n objects (which could be numbers, strings, or any other objects that can be compared with each other), and suppose we wish to arrange these objects in ascending order in an array a [n], so that a [0] <= a[1] <= . . . <=a[n-1]. A straightforward algorithm to accomplish this is described in pseudo-code below:

for(i = 0; i < n; i++)
{
j = index of the smallest object in S;
a[i] = Sj;
Sj = infinity;
}

Observe that setting Sj = infinity in the pseudo-code above means marking the corresponding object as "already sorted," and effectively deleting it from S. For example, if the objects in S are represented as pointers, you might set the value of the corresponding pointer to NULL, and make sure that NULL pointers are excluded when computing the index of the smallest object in S.

The objects you are asked to sort in this problem are words, represented as strings of characters. To compare two words alphabetically, you should use the strcmp standard library function. Note that

strcmp ("apples", "oranges") returns -1
strcmp ("oranges","apples") returns 1
strcmp ("apples", "apples") returns 0

There is more information on strcmp in Section 10.11 of our Zybook. Finally, note that in this problem, you are required to comply with the original ANSI C standard from 1989 (use the flags-std=c89 and -pedantic-errors when compiling with gcc). This implies that variable-length arrays whose size is determined at runtime are not allowed. Instead, use pointers and dynamic memory allocation.

Input

The program should read its input from the file alphabetic_sort.dat. The first line of this file contains a single positive integer n, which specifies the number of words to be sorted. The first line is followed by n more lines. Each of these n lines consists of two fields separated by whitespace. The amount and kind of whitespace (e.g., blanks, tabs) could vary from line to line. The first field contains a positive integer l, which specifies the length of the word to follow in the second field. The second field is the word itself, which could be any contiguous sequence of l letters. For the purposes of this problem, a letter is a character from the set {a,b,. . ., z} whose ASCII code is in the range [97-122).

Thus all the letters appear in lower case. Finally, each line is terminated by the newline character n, which appears right after the word. A sample file alphabetic-sort.dat is given below:

9
5 apple
58 mndoipsuewrwsfsdkjoewrernpowrqaldrrebnsfsrfereewnqewrezera
1 a
6 orange
5 peach
5 apple
4 pear
10 grapefruit
7 oranges

You do not need to check the validity of the input file: you can assume that it conforms to the specifications detailed above. You can also assume that this file contains at least 2 lines (that is, at least 1 word).

Observe that the number n of words to be sorted and the lengths (1,12,. . .,ln of the words themselves are not limited in any way. For the purposes of this problem, a word is any sequence of letters, and this sequence could potentially be arbitrarily long. The only guarantee on the input to your program is as follows: the total number of bytes needed to store all the words in the input file, using dynamic memory allocation, will not exceed the memory resources of your computer.

Output

The program should write its output to the file alphabetic_sort.out. The output should consist of the list of words in the input file, printed one per line, in ascending alphabetical order. A sample output file alphabetic-sort.out that results upon processing the input file above, is shown below:

a
apple
apple
grapefruit
mndoipsuewrwsfsdkjoewrernpowrqaldrrebnsfsrfereewnqewrezera
orange
oranges
peach
pear

Notes

• You can use any functions you like from the C standard library. The header file < stdio.h> is already included in exam_template.c. If you would like to use standard library functions other than those declared in < stdio.h>, you should #include the corresponding header files. In this problem, you will need functions declared in < stdlib.h> (for dynamic memory allocation) and in < string.h> (for alphabetic string comparison).
• You can use any algorithm to do the sorting. However, if you use a sorting algorithm different from the one given on the first page herein, please state this and clearly explain you algorithm in a comment. This would make it much easier to grade your source code.
• Note that when compiling with gcc using the -std=c89 and -pedantic-errors flags, as you are required to do in this problem, you cannot use the // style of comments. In the ANSIC standard, only /* */ comments are allowed.
• Try to make your code easy to follow and understand: choose meaningful names for identifiers, use proper indentation, and provide comments wherever they are useful. While this is not required, it could help you receive partial credit: source code that is not correct and is also difficult to understand will receive zero credit, even if it is partially correct.