Write a Python method sort() to sort a LinkedList object in descending order of

Question

Write a Python method sort() to sort a LinkedList object in descending order of the attribute _value. The code for the LinkedList class is shown below and also on the assignment web page. You should use the sorting algorithm described here.

Given a LinkedList object llist, the execution of the code

llist.sort()
print(llist)

should cause the sorted list to be printed out.

## DON'T EDIT ANY CODE OTHER THAN THAT OF THE sort() METHOD YOU WRITE.
class LinkedList:
def __init__(self):
self._head = None
  
# sort the nodes in the list
def sort(self):
# your code here <<<
  
# add a node to the head of the list
def add(self, node):
node._next = self._head
self._head = node
  
# remove a node from the head of the list and return the node
def remove(self):
assert self._head != None
_node = self._head
self._head = _node._next
_node._next = None
return _node
  
# insert node2 after node1
def insert(self, node1, node2):
assert node1 != None
node2._next = node1._next
node1._next = node2
  
def __str__(self):
string = 'List[ '
curr_node = self._head
while curr_node != None:
string += str(curr_node)
curr_node = curr_node.next()
string += ']'
return string

class Node:
def __init__(self, value):
self._value = value
self._next = None
  
def __str__(self):
return str(self._value) + "; "
  
def value(self):
return self._value
  
def next(self):
return self._next
  
"""DO NOT MODIFY ANYTHING BELOW THIS LINE"""
def test01():
ll = LinkedList()
ll.add(Node(1))
ll.add(Node(3))
ll.add(Node(2))
ll.sort()
return str(ll)

def test02():
ll = LinkedList()
ll.add(Node(17))
ll.sort()
return str(ll)

def test03():
ll = LinkedList()
ll.sort()
return str(ll)

def test04():
ll = LinkedList()
ll.add(Node(1))
ll.add(Node(1))
ll.add(Node(1))
ll.sort()
return str(ll)

def test05():
ll = LinkedList()
ll.add(Node(3))
ll.add(Node(2))
ll.add(Node(1))
ll.sort()
return str(ll)

def ll_sort(test_num):
test_func = globals()['test{0}'.format(test_num)]
return test_func()

Explanation / Answer

CODE:

def sort(self):

    cur = self._head

    while True:

        flag = False

        while cur:

            try:

                if cur._value < cur._next._value:

                    temp = cur._value

                    cur._value = cur._next._value

                    cur._next._value = temp

                    flag = True

            except AttributeError:

                pass

            cur = cur._next

        if flag == False:

            break

        else:

            cur = self._head

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.