Lab #2 Comparing Sorting Algorithms Solution



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

    1. Private properties of: year (int), month (int), day (int)

    1. A setter with an int parameter formatted as: YYYYMMDD that updates the internal year, month and day using the int parameter

    1. Methods (at least):

      1. Print the date as YYYYMMDD

      1. 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)

  1. (15) Create a Class to represent a Person

    1. Private properties of: ssn (int), firstName (string), lastName (string), birthday (Date)

    1. Constructor to create a Person given ssn (string), firstName (string), lastName (string), birthdate (string YYYYMMDD)

    1. Methods (at least):

      1. Print the Person

      1. Get the age of the Person

  1. (10) Write a function to read the data for a Person from a file and creates an array of Persons

  1. (10) Test this by using the database1.txt file (has 1000 entries)

    1. Read in all the people and print out the array

  1. (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):

    1. Selection sort

    1. Insertion sort

    1. Bubble sort

    2. Shaker sort

  1. (10) Time how long each sort takes (just the sorting, not the file reading)

    1. 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

    1. Graph the times vs. the size of the data

    1. Comment on the differences

Extra Credit: Part #3: Sorting sorted data (10)

  1. For each of the sorting algorithms

    1. Read the unsorted data

    1. Sort and time the sorting of the unsorted data

    2. Sort and time the sorting of the sorted data

    1. 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)

  1. Tabulate the results

  1. Comment on the times for sorting unsorted data, sorting sorted data and sorting sorted data into the opposite order for each of the algorithms.

error: Content is protected !!