Question

Search Exercise 11.A: Mergesort with a Comparator CS 1410 Background The sort algorithms we have looked at in Module 8 have all sorted list elements in ascending because it compares elements with the less-than operator. For example, in our mergesort program, the comparison appears as follows: 18 L[1] R01 The effect of this comparison is that if L(i) is less than RC), then L[is considered to come before R[i] in the sorted result. Hence the ascending order of the output. If we were to change to comparison to greater than 1f L[1] > RE: which is the same as if R[1] <L[1]: then R[i] will precede Li) in the result yielding results in descending order. In this exercise, you will change mergesort to accept two parameters: the list to sort, and a comparator function, which takes as parameters the two items for mergesort is comparing. Your function will return True if the first parameter precedes the second in the desired ordering. By using a function as a parameter, you can sort lists by any desiring ordering, no matter how complex. Data The data to sort is in the file data.csv in the Exercise 11A folder in Canvas. It is similar to employees.csv from Project 5, except the header row has been removed and an extra data record has been inserted. You will read this file into a list of tuples. Requirements Copy the code from mergesort.py to a new file named sort.py. In mort.py, modify mergesort to take a second parameter, which will be a binary function. In the updated mergesort, refer to that binary function whenever two items are being compared during the sorting. You only have to modify 4 lines of code. You can verify that your function is working if the following code gives the output indicated below...

In Python!

Answer 1

I have atttached the code. It has comments for explanation. If you have any queries, feel free to comment.

Program Screenhots for Indentation Reference:

import msort def comparator_by_name (x, y): k = x[1].split() # split to put in tuple 1 y[1].split() return (k[-1], k[0]) < (1[-1], 1[0]) ## open the file for reading lines [] with open ("data.csv", "r") as f: ### read all the lines for line in f: ## get a line and split by comma i line.split(',') ## append to lines lines.append(1) ## sort using the id = sort by id with open ("data_by_id.txt", "W") as f: sorted data lines.copy() ## make a copy msort.mergesort(sorted_data, lambda x, y: x[0] < y[0]) ## use id as the key for line in sorted data: f.write(str(tuple(line)) + "\n") ## writes the lines sort by name with open ("data_by_name.txt", "W") as f: sorted lines.copy() ## make a copy msort.mergesort(sorted_name, comparator_by_name) use tuple as the comparator for line in sorted name : f.write(str(tuple(line)) + "\n") ## writes the lines

#Mergesort: = def mergesort(arr, key=lambda x, y: x < y): if len(arr) >1: # Sort halves ito separate memory mid len (arr) // 2 L arr[:mid] arr[mid:] mergesort(L, key) mergesort(R, key) = # Merge L and R back into arr i = j = k = 0 = ## put using the key while i < len(L) and j < len(R) : if key (L[i], R[j]): # put ith item arr[k] L[i] i+=1 else: arr[k] R[j] j+=1 k+=1 # Checking if any elements were left while i < len(L): arr[k] = L[i] i+=1 k+=1 while j len(R): arr[k] = R[j] j+=1 k+=1

Sample Output (On a part of file):

Program code to copy:

msort.py:

def mergesort(arr, key=lambda x, y: x < y):
    if len(arr) >1:
        # Sort halves ito separate memory
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        mergesort(L, key)
        mergesort(R, key)

        # Merge L and R back into arr
        i = j = k = 0

        ## put using the key
        while i < len(L) and j < len(R):
            if key(L[i], R[j]):
                # put ith item
                arr[k] = L[i]
                i+=1
            else:
                arr[k] = R[j]
                j+=1
            k+=1

# Checking if any elements were left
        while i < len(L):
            arr[k] = L[i]
            i+=1
            k+=1
        while j < len(R):
            arr[k] = R[j]
            j+=1
            k+=1

ex11a.py:

import msort

def comparator_by_name(x, y):
    k = x[1].split() # split to put in tuple
    l = y[1].split()
    return (k[-1], k[0]) < (l[-1], l[0])

## open the file for reading
lines = []
with open("data.csv", "r") as f:
    ### read all the lines
    for line in f:
        ## get a line and split by comma
        l = line.split(',')
        ## append to lines
        lines.append(l)
    ## sort using the id
  
# sort by id
with open("data_by_id.txt", "w") as f:
    sorted_data = lines.copy() ## make a copy
    msort.mergesort(sorted_data, lambda x, y: x[0] < y[0]) ## use id as the key
    for line in sorted_data:
        f.write(str(tuple(line)) + "\n") ## writes the lines

# sort by name
with open("data_by_name.txt", "w") as f:
    sorted_name = lines.copy() ## make a copy
    msort.mergesort(sorted_name, comparator_by_name) ## use tuple as the comparator
    for line in sorted_name:
        f.write(str(tuple(line)) + "\n") ## writes the lines