Introduction: For this assignment you have to write a c program that will utilize the merge sort and binary search algorithm.
What should you submit?
Write all the code in a single .c file and upload the .c file.
Please include the following lines in the beginning of your code to declare that you are the author of the code:
/* COP 3502C Final term Assignment 1
This program is written by: Your Full Name */
Compliance with Rules: UCF Golden rules apply towards this assignment and submission. Assignment rules mentioned in syllabus, are also applied in this submission.
Do not post or share part or full solution of your assignment anywhere!
Problem
In this assignment, you have to read a text file (in.txt) that contains a set of point coordinates (x, y). The first line of the file contains the number of points (N) and then each line of the file contains x and y values that are separated by space. The value of x and y are integer. They can be both negative and positive numbers. You have to sort those points in x-axis major order (it means it will be sorted based on x first, if multiple point has same x, then it will sort based on y) and then write the output into another file (out.txt) in the same format, i.e., each line contains one coordinate point x and y and they are space delimited. After writing the sorted points in the file, your program should display the message “sorted and output written”. After that your program should continuously prompt the user for an input coordinate point x and y values and your program should perform binary search to determine whether the point exists in the given list of points. If it is found, it should show “Found” and record number. The program will stop prompting for x and y, if the search input x=-999 and y=-999
Example
Sample Input file in.txt:
7
100 2
99 -22
6 3
4 6
2 7
2 5
-5 2
Sample output file out.txt:
-5 2
2 5
2 7
4 6
6 3
99 -22
100 2
“Sorted and output written”
Search input (x y): 2 3
Output: Not found
Search input (x y): 4 6
Output: Found at record 4
Search input (x y): 2 7
Output: Found at record 3
Search input (x y): 2 5
Output: Found at record 2
Search input (x y): -999 -999
Output: exit
Requirement:
You must use file IO, Merge sort and binary search for your solution.
Your program must compile in Eustis.
Rubric:
1) Reading input file and storing data into appropriate types of variables: 1
2) Applying Merge sort properly and writing results into out.txt file: 7
3) Performing Binary search properly and output: failing each test case -2 points. Total 6
Please see the lecture slides and uploaded codes for learning merge sort and binary search and File I/O.
Remember, we have done one lab on File I/O. We have used fscanf and fprintf while reading and writing to file, respectively. For file I/O reference, see Week 2 module and Lab of Week 2.
