CPTS Python

Generate sample data as Numpy ndarray using one or more Numpy methods. For instance, you can use numpy.random.randint() method to generate an array of random values.

Create a Python List using the sample data. The Python List would be sorted using different sorting algorithm as described below.

Generate at least 9 different data sets (3 sorted/unsorted order * 3 data sizes) as described below:

Sorted / Unsorted order:

An already sorted array in ascending order

An already sorted array in descending order

An unsorted array in random order

Data Size:

250

500

1,000

(more values if your computer can handle)

Note: Make sure to re-create the Python List with the same NumPy ndarray for each sorting routine! This is important in order to compare the results of the different algorithms.

Sorting Routines

Implement 4 traditional and 2 divide-and-conquer sorting routines (implement them either as individual functions or as methods of a class):

Traditional Algorithms (4)

Selection sort

Bubble sort

Insertion sort

Shell sort

Divide-and-Conquer Algorithms (2)

Merge sort

Quick sort

Each sorting routine should measure execution time, data comparison count, and data swap count metrics. Note that 1 data swap operation typically involves 3 assignment operations. It should return these metrics at the end of the sorting routine.

Storing Metrics and Program Output

The program should generate metrics for each combination of the data set and sorting routine. Pictorially, here is an example table with the data sets and sorting algorithm metrics:

Write the contents of the sorting results to a CSV file with a filename sort_results.csv.

Program Flow

Write a main() function that performs the following tasks:

Generate a sample data with one of the configuration combination (sorted/unsorted configuration with data size configuration)

Create a Python List with the sample data

Sort the Python List using a sorting routine. The sorting routine should also measure and return sorting metrics

Store the results of the sorting metrics temporarily in a data structure of your choice (eg. Python List or Dictionary). Output the sorting metrics to a CSV file

Repeat the process of generating the sample data, creating a Python List, sorting the list and outputting the metrics for each configuration

Call the main() function in your program.