ECE 218 Lab #2 Comparing Sorting Algorithms solution




5/5 - (4 votes)

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)
1. (10) Create an Class to represent a Date
a. Private properties of: year (int), month (int), day (int)
b. A setter with an int parameter formatted as: YYYYMMDD that updates
the internal year, month and day using the int parameter
c. Methods (at least):
i. Print the date as YYYYMMDD
ii. 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)
2. (15) Create a Class to represent a Person
a. Private properties of: ssn (int), firstName (string), lastName (string),
birthday (Date)
b. Constructor to create a Person given ssn (string), firstName (string),
lastName (string), birthdate (string YYYYMMDD)
c. Methods (at least):
i. Print the Person
ii. Get the age of the Person
3. (10) Write a function to read the data for a Person from a file and creates an
array of Persons
4. (10) Test this by using the database1.txt file (has 1000 entries)
a. Read in all the people and print out the array
5. (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)
1. (40) Sort the array of Persons by age using each of the following algorithms
(implement these algorithms):
a. Selection sort
b. Insertion sort
c. Bubble sort
d. Shaker sort
2. (10) Time how long each sort takes (just the sorting, not the file reading)
a. 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
b. Graph the times vs. the size of the data
c. Comment on the differences
Extra Credit: Part #3: Sorting sorted data (10)
1. For each of the sorting algorithms
a. Read the unsorted data
b. Sort and time the sorting of the unsorted data
c. Sort and time the sorting of the sorted data
d. 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)
2. Tabulate the results
3. Comment on the times for sorting unsorted data, sorting sorted data and
sorting sorted data into the opposite order for each of the algorithms.