Comp 110 Assignment 7    Sorting and Searching

7 points + 6 extra points

Demonstrate by yourself. After demonstration, send the source code to me through email.

Assigned: Friday, July 20
Due: Thursday, July 26  

In this assignment You will write programs to read students' names and scores from a file and do sorting and searching on the data. 

The students' name and scores are stored in a file, following this format:

(line 1) Number_of_Students
(line 2) name1 score1
(line 3) name2 score2
(line 4) name3 score3
etc.

An example of the input file is input.txt

Requirements:

A. (2 points) Sort the information of the file according to the scores of the students. The scores are sorted in the descending order( from high to low). Save the sorted information to a file. The format of the output file is the same as the input file. For example, the output of the input.txt is SortScore.txt. 

B. (2 points) Sort the information of the file according to the names of the students. The names are sorted in the alphabetic order (use compareTo method defined in String class). Save the sorted information to a file. The format of the output file is the same as the input file. For example, the output of the example input is SortName.txt. 

C. (3 points) Sort the information of the file according to the names of the students. The names are sorted in the alphabetic order. Use binary search to find the score and the grade for a given name. If there are several students with the same name, the program only needs to find one of them. The user interaction is the same as assignment 4, question 4. 

Please test above programs with files which have 200 and 2000 students. The files are input1.txt and input2.txt.

Extra Points:

1. (3 points) Read the Heap Sort algorithm in the wikipedia and implement the requirement A using Heap sort.

2. (3 points) Read the Quick Sort algorithm in the wikipedia and implement the requirement A using Quick sort.

Hints:

1. The example program of sorting and search  can be found at the class practice.

2. The example program of reading and writing files can be found at the class practice.

3. The user interaction code in assignment 4 question 4 can be re-used to finish requirement 3.

4. Try to use Array of Objects. Define Student as a class, which has name and score data member. Implement two version of comparison methods: one is based on the score and another is based on the name.

5. Figure out the meaning of the code Student.java and sortStudent.java.