Please Help me write a sort( ) method for this question. Based on the algorithm in picture:

The Basic classes code are provided below

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:

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.

Suppose that, initially, the list to_be_sorted is the following: sortedhead 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 cii 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