Question

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!!)

Answer 1

def printOrder(arr, n, k):

  

    len1 = k

    len2 = n - k

    arr1 = [0] * k

    arr2 = [0] * (n - k)

  

    # Store the k elements

    # in an array

    for i in range(k):

        arr1[i] = arr[i]

  

    # Store the remaining n-k

    # elements in an array

    for i in range(k, n):

        arr2[i - k] = arr[i]

  

    # sorting the array from

    # 0 to k-1 places

    arr1.sort()

  

    # sorting the array from

    # k to n places

    arr2.sort()

  

    # storing the values in the

    # final array arr

    for i in range(n):

        if (i < k):

            arr[i] = arr1[i]

  

        else :

            arr[i] = arr2[len2 - 1]

            len2 -= 1

      

    # printing the array

    for i in range(n):

        print(arr[i], end = " ")

  

# Driver code

if __name__ == "__main__":

    arr = [ 5, 4, 6, 2, 1,

            3, 8, 9, -1 ]

    k = 4

  

    n = len(arr)

  

    printOrder(arr, n, k)

output::

2 4 5 6 9 8 3 1 -1