CSc 120: LinkedList sort method

Background

There are many sorting algorithms, such as quick sort, merge sort, and insertion sort, however, for this problem, we will use the algorithm described here.

Expected Behavior

1. Use input() (without any argument) to read the name of an input file. The file will consist of a single line of integers separated by spaces. Read the contents of this file into a Python list of elements, splitting at whitespace.
2. Create a LinkedList.
3. For each value value in the Python list created in step 1, create a node using the Node() method and add it to the LinkedList.
4. Use your sort method to sort the linked list and print the resulting sorted linked list using print(). Note: You must use the provided __str__(self) method so that your output matches the expected output of the autograder. Do not change the __str__(self) method.

Input

Output

The output consists of the sorted linked list as represented by the str() method. For the example file shown above, the output is

List[ 24; 19; 17; 8; 8; 5; 2; 2; ]

Programming Requirements

1. Your program must use the LinkedList and Node classes in the starter code found here: linkedlist_starter.py
2. To sort a linked list, your program must use the algorithm described here. In that algorithm, notice that the nodes are moved, one at a time, from the orignal list to a new list that is kept sorted. That is, the nodes are moved, not copied. Also, you must move the nodes and not simply swap the value attributes. (Solutions that swap the value attributes will not get full credit.)
3. Write the sort() method for the LinkedList class, using the sorting algorithm given above.

class LinkedList

An object of this class represents is a Linked List.

• def sort(self) : sorts the LinkedList object referred to by self in descending order of the _value attributes.

4. Do not modify any of the other methods provided in the starter code.
5. Do not use a Python list for sorting. Submissions that attempt to by-pass writing the linked list sorting method using the algorithm given will not receive credit.
6. The only Python list allowed in this program is the list resulting from splitting the line in the input file.

Errors

Commenting

1. You need a header file as ususal.
2. Since you were given the code for the LinkedList and Node classes, you do not need to comment them for this assignment. You only need to provide a docstring the for sort() method that you write.

Examples