In Python

For this programming assignment, we are going to investigate how much "work" different sorting routines do, based on the input size and order of the data. We will record the work done by writing output CSV (comma separated value) files and creating various plots using matplotlib.

Note: for this assignment, do not use Jupyter Notebook to code your solution. Use standard .py files and save your output to .csv and .png files (see the program details below for more on program output).

Program Details:

Data Structure Implement a doubly linked circular linked list of Node objects called CircularDoublyLinkedList.

The data of each Node in the list is an integer. You will collect measurements for: An already sorted linked list An already sorted linked list in descending order A linked list containing random data List Size Configurations Generate each of the above linked lists with the following number of nodes: 500 1000 5000 10000 (more values if you wish)

Note: Make copies of the original lists (as necessary) and pass the copies to each sorting routine so each routine is operating on the same data!

This is important in order to compare the results of the different algorithms. Sorting Routines Implement 3 of the following linked list sorting routines (implemented as a function or as a method of your CircularDoublyLinkedList class): Choose 2 from the first 4 and 1 from the last 2 Selection sort Early exit bubble sort (stops when the list is sorted) Insertion sort Shell sort Merge sort Quick sort Data to Collect For each sorting routine above, create a pandas DataFrame with rows for each list size configuration and columns for each metric to collect.

The metrics to collect include the algorithm's execution time using timeit and counts for the following operations: Number of data comparisons Number of loop control comparisons Number of assignment operations involving data Number of assignment operations involving loop control "Other" operations (operations that don't fall into one of the above categories) Total number of operations (sum of the above)

Note: Be sure to comment everything you count in your code. Pictorially,

here is an example DataFrame for a sorting routine:

List configuration Seconds # Data # Loop # Data assignments # Loop assignments # Other

Total Sorted N=500

Sorted N=1000

Sorted N=5000

Sorted N=10000

Descending sorted N=500

Descending sorted N=1000

Descending sorted N=5000

Descending sorted N=10000

Random N=500 Random

N=1000 Random N=5000

Random N=10000

Program Output CSV Files Write the contents of each sorting routine DataFrame to a CSV file with a filename of the form _sort_results.csv.

For example, bubble_sort_results.csv. See the function to_csv() in the pandas library for a straightforward way to do this! In total, your program should output 6 csv files, one for each sorting routine. Plots to Generate For each of the three list configurations (sorted, descending sorted, random), create two plots with list size on the x-axis (i.e. 500, 1000, 5000, 10000) and the following on the y-axis: Plot 1: running time Plot 2: total operation count Each plot should have a separate curve for each sorting routine. For example (example purposes only!!)