Ex16 figuring out merge_sort

I am trying to figure out how to make the merge_sort algorithm with the use of double linked lists, but I am bumping into an error that says I need to use an extra positional argument (which I think is self).

This is the code:


from ex16 import ex14

def merge_sort(numbers):

    #if length of m <_ 1 then
        #return m

    if numbers.count() <= 1:
        return numbers

    #var left := empty list
    left_list = ex14.DoubleLinkedList
    #var right := empty list
    right_list = ex14.DoubleLinkedList

    #for each x with index i in m do
        #if i < (length of m)/2 then
            #add x to the left
            #add x to right
    nodes = numbers.begin
    while nodes:
        if numbers.begin.data >= numbers.count():
        nodes = nodes.next

    # left := merge_sort(left)
    leftmerged = merge_sort(left_list)
    # right := merge_sort(right)
    rightmerged = merge_sort(right_list)
    #return merge(left, right)
    return merge(leftmerged, rightmerged)

def merge(left, right):

    #var result := empty list
    result = []

    #while left is not empty and right is not empty do:
        #if first (left) <_ first(right) then:
            #append first(left) to result
            #left := rest(left)
            #append first(right) to result
            #right := rest(right)
    while left > 1 and right > 1:
        if left[0] <= right[0]:
            left = left[1:]
            right = right[1:]

    #while left is not empty do:
        #append first(left) to result
        #left := rest(left)
    while left > 1:
        left = left[1:]

    #append first(right) to result
    # right := rest(right)
    while right > 1:
        right = right[1:]

    #return result
    return result

doublelinkedlist with create function

class DoubleLinkedListNode(object):

    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoubleLinkedList(object):

    def __init__(self):
        self.begin = None
        self.end = None


from ex16 import sorting
from ex16 import ex14
from random import randint

max_numbers = 30

def test_merge_sort():
    numbers = random_list(max_numbers)


    assert is_sorted(numbers)

The code that is not working is marked with arrows.

I get the following error:

TypeError: create() missing 1 required positional argument: ‘obj’

I am guessing that the extra argument it needs is the self, which I did not need to use when I was working in the module itself. However, if I type in self, I get the following error:

NameError: name ‘self’ is not defined

So what am I missing here?

This is kind of an interesting one. I’ll give you just a hint:

left_list = ex14.DoubleLinkedList

Now left_list is the same thing as ex14.DoubleLinkedList, right? So what exactly is it?

Haha. Ok thank you, I’ve figured out the problem. However, I could not give en exact answer to your question.

left_list = ex14.DoubleLinkedList

This definetly made something, otherwise it would error. But what it made? I don’t know.

PS: Do you have any tips for printing out something in a test? I don’t know how to print out something which I suspect is being problematic.

left_list becomes a synonym for the class. After you’ve done this you could do my_list = left_list() to get an instance. They like to say that classes are “first-class objects” in Python. It means that you can pass classes around like anything else.

I don’t have time now to read through the rest of your post. Will do later if I can.

Allright, And what was the practical difference between a synonym and an instance again?

Also, I checked the cheatsheet and saw that I was way of track, so I deleted the rest of the post and started working with the cheatsheet. I didn’t totally copypaste, but tried to adjust what I already had.

So the cheatsheet looks like this:

Schermafbeelding 2021-05-20 143528

So what do these two lines of code do?

    if left == None: return right
    if right == None: return left

Where do they return the right and the left? Shouldn’t the leftover lefts and rights be added to the result? Or are they?

Ok, synonym was a bad word choice. When you assign a class to a variable, that variable contains the class, not an instance of the class.

Well, the returned value ends up in the line result.next = merge(left, right.next) (or the other way around) one step up in the recursive call chain.

Are you using pytest? I believe it has a an option to not hide output from your test functions.

A free service run by Zed A. Shaw for learncodethehardway.org.