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.

assignment web page:

Expected Behavior

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. 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.

The code for the LinkedList class is as follows:

class Node: def __init__(self, value): self._value = value self._next = None # getter for the _value attribute def value(self): return self._value # getter for the _next attribute def next(self): return self._next def __str__(self): return str(self._value) + "; " class LinkedList: def __init__(self): self._head = None # 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

Examples

Code:

ll = LinkedList() ll.add(Node(1)) ll.add(Node(3)) ll.add(Node(2)) ll.sort() print(ll)

Result: (this is the string returned by the __str__() method for the LinkedList class)

List[ 3; 2; 1; ]

Code:

ll = LinkedList() ll.sort() print(ll)

Result:

List[ ]

Code:

ll = LinkedList() ll = LinkedList() ll.add(Node(1)) ll.add(Node(1)) ll.add(Node(1)) ll.sort() print(ll)

Result:

List[ 1; 1; 1; ]

algorithm:

CSc 120: Sorting Linked Lists

We will use an intuitively simple algorithm to sort linked lists. The essential idea is the following. Given a linked list to_be_sorted to sort, the algorithm repeatedly moves nodes from the original list to_be_sorted to a new list sorted, maintaining the invariant that sorted is always kept in sorted order (i.e., for the purposes of this assignment, in descending order by count of the number of occurrences of each word).

Data structures

The algorithm has a linked list, sorted, which contains all of the nodes that have been sorted so far.

Initially, sorted is empty (i.e., sorted._head has the value None). Each iteration of the algorithm (step 2 below) adds a node to this linked list. The algorithm maintains the invariant that this list is always kept in sorted order.

Algorithm

The algorithm repeatedly performs the following steps:

Remove a node, call it curr_element, from the head of to_be_sorted.

Iterate down the list sorted to find the position where curr_element should be inserted such that, after curr_element has been inserted, sorted remains in sorted order.

Insert curr_element at that position in sorted. This results in one more element being placed in sorted order in the sorted list.

The iteration stops when all elements have been moved from to_be_sorted to sorted. At that point, to_be_sorted will have the value None and sorted will have all of the nodes in sorted order. The algorithm then copies the list sorted to the head of to_be_sorted.

The key step in the algorithm above is step 2. The logic for this step is as follows. Here, we follow the requirement for this assignment that the list should be sorted in descending order. We say that an element A is "smaller than" an element B if A's count is less than B's count.

If sorted is empty: add curr_element to the head of sorted.

Otherwise, if the first element of sorted is smaller than curr_element: add curr_element at the head of sorted (so curr_element becomes the new first element).

Otherwise, iterate down sorted to find an element E satisfying the following:

E ? curr_element; and

either E._next curr_element, or E._next is None.

(The simplest way I can think of to do this uses two loops one after another: first, iterate down sorted to find the first node whose count is smaller than curr_element, call this node E1; second, iterate down sorted again to find the node E just before E1.)

Insert curr_element immediately after E.

Example

Suppose that, initially, the list to_be_sorted is the following:

Iteration 1

The first iteration of the algorithm moves the first element from to_be_sorted for insertion into sorted:

Since sorted is empty (Item a in the algorithm above), curr_element is added to it as its only element:

Note that this preserves the invariant that sorted is in sorted order.

Iteration 2

The algorithm again moves the (current) first element from to_be_sorted:

Since this element is bigger than the first element of sorted (Item b in the algorithm above) it is inserted at the head of sorted:

Note that, again, this preserves the invariant that sorted is in sorted order.

Iteration 3

The algorithm once again moves the (current) first element from to_be_sorted:

Since this element is smaller than the first element of sorted (Item c in the algorithm above), the algorithm iterates down sorted to find the position where it should be inserted. In this case, item c.ii of the algorithm applies, with E._next == None; i.e., curr_element is inserted at the end of sorted:

Note that, again, this preserves the invariant that sorted is in sorted order.

This process is repeated with the remaining elements of the linked list to_be_sorted.

code:

## 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

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