CMSC--202 Computer Science II for Majors
Fall 1997 22 November 1997 Homework 8

The purpose of this homework is to give you some experience with the qsort routine available in most C libraries. It will also introduce you to an array-sorting method that involves pointers into a fixed, unsorted array.

Background

The Air Force has been compiling a database of Martian space-travelers in residence at Roswell, New Mexico. It's a simple data-base composed of first name, last name, and MSSN (martian social security number). Unfortunately, searching the database is difficult because it is not sorted in any way. Your task is to provide three sorted lists of Martians, one by first name, one by last name, and one by MSSN. The Air Force has determined that Martian names and SSNs follow these rules:

1. Martian names consist of lower case alphabetic characters, except that the last character is always upper case.
2. Martian first names do not exceed 10 characters in length.
3. Martian last names do not exceed 20 characters in length.
4. Martian SSNs are always exactly 9 digits long and never start with a zero.

Sample output from the program is given on page .

Program Tasks

1. Your program is to take an integer on the command line. This integer is the number of martians to be in the data base. Erroneous command line arguments are to result in a usage message (to stderr) and exit from the program.

2. Elements of the data base are to be structs of three fields (first name, last name, and MSSN).

3. Dynamically allocate an array of pointers to data base elements ( i.e., pointers to struct). The size of this array is given by the number entered on the command line. This is the data base. IT IS NEVER SORTED.

4. Since the Air Force database is top secret, you will have to randomly generate the appropriate data base elements. Data base elements are to be dynamically allocated. Each pointer in the array of pointers is to be assigned to a data base element.

5. Dynamically allocate three other arrays. Each is the same size as the data base array. The elements of these arrays are pointers to the elements of the data base array.

6. Print the data base unsorted.

7. Sort the three arrays ( NOT the data base array) using qsort. You will have to write the appropriate comparator(s) for qsort. The prototype for qsort is in stdlib.h.
   1. the first array is sorted so its elements point to the data elements in increasing first-name order,
   2. the second array is sorted so its elements point to the data elements in increasing last-name order,
   3. the third array is sorted so its elements point to the data elements in increasing SSN order.

The following figure illustrates how an array of pointers can be sorted so its elements point to the data in another array in increasing numerical order. The ``data'' array contains integers in no particular order. The ``pointer'' array contains pointers sorted so they point to the elements of the ``data'' array in increasing order. The first pointer points to the integer with lowest value; the second pointer points to the integer with the next higher value, and so forth. The last pointer points to the integer with highest value.

In this homework, there will be three separate arrays of pointers and the data array will not contain integers, but the idea is the same as shown in the figure. There are two major advantages to sorting pointers rather than the data itself.

1. The pointers generally don't take as much storage as the data, so they can be moved around more easily. Moving large data elements can take a long time.
2. Multiple arrays of pointers can be used to point to the same data set. Each array represents a different sorting order of the data.

Hints

Remember that the rint202(int low,int high) function returns a random integer between low and high, inclusive. Since a char is an integer type, rint202 can be used to return a random character in a given range.

Sample Run

  Here is a sample of the output generated by the hw8 program. The Martian data base is printed four times: unsorted, sorted by first name, sorted by last name, and sorted by MSSN.

>> hw8 
hw8 <number of martians>

>> hw8 foo
Command line argument must be an integer

>> hw8 5

----- Before Sorting -----

Last Name           First Name  Mars SSN 
tirtxQ              kfobtevfyV  446634851
geigblzjcvhU        cvalficJ    195842815
rqmerxjmgdlgaegkrnE lnxxvfbgiJ  689424177
qviE                ihtyV       776036814
fdnhlucmscenK       fcezoC      266260041

----- Sorted by First Name -----

Last Name           First Name  Mars SSN 
geigblzjcvhU        cvalficJ    195842815
fdnhlucmscenK       fcezoC      266260041
qviE                ihtyV       776036814
tirtxQ              kfobtevfyV  446634851
rqmerxjmgdlgaegkrnE lnxxvfbgiJ  689424177

----- Sorted by Last Name -----

Last Name           First Name  Mars SSN 
fdnhlucmscenK       fcezoC      266260041
geigblzjcvhU        cvalficJ    195842815
qviE                ihtyV       776036814
rqmerxjmgdlgaegkrnE lnxxvfbgiJ  689424177
tirtxQ              kfobtevfyV  446634851

----- Sorted by Mars SSN -----

Last Name           First Name  Mars SSN 
geigblzjcvhU        cvalficJ    195842815
fdnhlucmscenK       fcezoC      266260041
tirtxQ              kfobtevfyV  446634851
rqmerxjmgdlgaegkrnE lnxxvfbgiJ  689424177
qviE                ihtyV       776036814

Submit

Submit your work in the usual way, using the submit command. For example, to submit the file foo.c, do:

• Anastasio's sections: submit cs202_01 hw8 foo.c
• Edelman's sections: submit cs202_02 hw8 foo.c

Submit all the files required to successfully compile your homework using your submitted makefile. The only constraints on file names are that the executable must be named hw8 and the makefile must be named Makefile or makefile. Otherwise, you may name your files as you wish.