CSC 212 – Data Structures

CSC 212 – Data Structures

Sorting Assignment

You are to create a program that enables you to measure the execution times of various sorting algorithms to better understand their efficiency characteristics.

For each sorting algorithm, you are to measure and record the execution times for various lists of randomly generated integers.

The list sizes used for the test cases should start at 10,000, and go up by 10,000 for each test until the execution time for the test exceeds 60 seconds.

The algorithms for which you are to run the tests are:

• Selection sort

• Bubble sort

• Merge sort

• Tree sort (see

Implementations for the first 3 algorithms are available in the textbook.

For Tree sort, refer to the Wikipedia entry (link above) for a description of the algorithm. The implementation of the algorithm should be based on the tree definition in (posted on BlackBoard).

You are to report the execution times obtained for the algorithms in a table with the following format:

Note that since the algorithms have different efficiencies, execution times of over 60 seconds will be reached for different list sizes. Stop running tests for a given algorithm once it exceeds 60 seconds.

For each algorithm, create a line plot showing the list size on the x-axis and the execution time on the y-axis and include a discussion about whether the execution times obtained correspond to the big-O time efficiency of the algorithm.

What to submit?

Submit your source Python files and the docx (or pdf) file with the results

(Place the table, plots, and discussion in one docx or pdf file)

Leave a Reply

Your email address will not be published. Required fields are marked *