$24
In this assignment, you are going to test the performance of different sorting algorithms. You will test: Selection, Insertion, Bubble and Shaker Sort algorithms.
The data files are given as ‘database?.txt’, where ‘?’ represents the numbers of thousands of entries in the file. The data in the files is arranged as:
ssn first_name last_name date_of_birth
ssn first_name last_name date_of_birth
ssn first_name last_name date_of_birth
…
To Turn In:
A Word document that contains:
Basic compiling instructions for your code Screen shots for the execution of each sort routine
Graphs (you can do them in Excel and include the images)
Comments on the timing for each routine
Source Code (with comments as necessary)
Part #1: Basic Objects and Functions (50)
(10) Create an Class to represent a Date
Private properties of: year (int), month (int), day (int)
A setter with an int parameter formatted as: YYYYMMDD that updates the internal year, month and day using the int parameter
Methods (at least):
Print the date as YYYYMMDD
Calculate the age of a person whose birthday is on the internal date. (You do not have to exact, simple age by year is fine)
(15) Create a Class to represent a Person
Private properties of: ssn (int), firstName (string), lastName (string), birthday (Date)
Constructor to create a Person given ssn (string), firstName (string), lastName (string), birthdate (string YYYYMMDD)
Methods (at least):
Print the Person
Get the age of the Person
(10) Write a function to read the data for a Person from a file and creates an array of Persons
(10) Test this by using the database1.txt file (has 1000 entries)
Read in all the people and print out the array
(5) Make sure to design your program and functions so that number of entries read is easily adjusted; this includes the size of your array.
Part #2: Sorting unsorted data (50)
(40) Sort the array of Persons by age using each of the following algorithms (implement these algorithms):
Selection sort
Insertion sort
Bubble sort
Shaker sort
(10) Time how long each sort takes (just the sorting, not the file reading)
Tabulate the times (average of 3 runs) for each sorting algorithm for each of the database files
i. They contain 1000, 2000, 3000, 5000, 10,000, 20,000 entries
Graph the times vs. the size of the data
Comment on the differences
Extra Credit: Part #3: Sorting sorted data (10)
For each of the sorting algorithms
Read the unsorted data
Sort and time the sorting of the unsorted data
Sort and time the sorting of the sorted data
Sort and time the sorting of sorted data into the opposite order (i.e. time sorting data to descending order which is already sorted in ascending order)
Tabulate the results
Comment on the times for sorting unsorted data, sorting sorted data and sorting sorted data into the opposite order for each of the algorithms.