Questions about HW7

[maxinebaghdadi]

Fernanda and I had a few questions about the HW:

1. To clarify, the _merged function is simply adding the two lists, correct? Meaning we wouldn't have to use cmp_standard.
2. For the merged_sorted function, do we have to incorporate the previous functions?
3. For the merged_sorted function, can we use while loops or should we be using recursion?

Thank you :)

[mikeizbicki]

Hi Maxine and Fernanda (and everyone else)!

I hope you're all adjusting well to the coronavirus situation. If there's anything I can do to help smooth your transitions, let me know.

Questions 1+2: You should not be using the cmp_standard or cmp_reversed functions directly in any of the functions you implement. Instead, you should be calling the cmp function that is passed in as a parameter to your functions. For example, you might have code that looks something like:

def _merged(xs, ys, cmp=cmp_standard):
    if cmp(xs[0],ys[0]) == 0:
        do_something_here

By using the cmp function, you let the person who is using your code decide for themselves whether they want to use cmp_standard or cmp_reversed, because they can pass those functions as the cmp parameter. For example, to sort a list from lowest to highest, you would call:

merge_sorted(xs,cmp=cmp_standard)

but to sort from highest to lowest, you would call

merge_sorted(xs,cmp=cmp_reverse)

The test cases use both of these versions. So if you don't use the cmp function inside the functions you write, then you will be guaranteed to fail the test cases.

Question 3: The _merge function is allowed to use loops, but both the quick_sorted and merge_sorted functions must be implemented with recursion.

PS: I edited your comment to update the formatting. Whenever you are referencing a piece of code, that code must be in backticks (so all the function names should be in backticks). This ensures that it is 100% unambiguous which parts of your message are code and which are not.

[CurtisSalinger]

Following up on the cmp question, I have the _merge function written such that it passes all the cases and the merge_sorted where it passes the first case but not the case with cmp_reverse.

I am wondering if it is my implementation in _merge but I cannot find the point of failure.

This is my code for _merge

43      def _merged(xs, ys, cmp=cmp_standard):

 50     i = 0
 51     j = 0
 52     n = 0
 53     ret = []
 54     while i < len(xs) and j < len(ys):
 55         res = cmp(xs[i],ys[j])
 56         if res == -1:
 57             ret.append(xs[i])
 58             i += 1
 59         if res == 1:
 60             ret.append(ys[j])
 61             j += 1
 62         if res == 0:
 63             ret.append(xs[i])
 64             ret.append(ys[j])
 65             i += 1
 66             j += 1
 67 
 68     while i < len(xs):
 69         ret.append(xs[i])
 70         i += 1
 71 
 72     while j < len(ys):
 73         ret.append(ys[j])
 74         j += 1
 75 
 76     return ret

and this is for merge_sorted

 78 def merge_sorted(xs, cmp=cmp_standard):

 93     if len(xs) == 0:
 94         return xs
 95     if len(xs) == 1:
 96         return xs
 97     else:
 98         mid = len(xs)//2
 99         leftlist = xs[:mid]
100         rightlist = xs[mid:]
101         l = merge_sorted(leftlist)
102         r = merge_sorted(rightlist)
103         return _merged(l,r)

[lindseytam]

In line 101,102,103, I think you need to add cmp as input. This is because by default it is always using cmp_standard. For example, in line 101 try:

l = merge_sorted(leftlist, cmp=cmp)

[CurtisSalinger]

That worked! Thank you.