The assignment is to use selection sort by swapping nodes, not the values. When sorting algorithm changes the last node, it raises AttributeError, because it seems that first.next in def min_sort()does not seem to change and is None. Here is the code
class LinkedList:
class Node:
def __init__(self, data, next=None):
self.data, self.next = data, next
def __init__(self, seq):
self.front = self.Node(None)
curr = self.front
for value in seq:
curr.next = self.Node(value)
curr = curr.next
def swap(self, x, y):
first = self.front
while first.next is not None:
if first.next.data == x.data:
prevx = first
if first.next.data == y.data:
prevy = first
first = first.next
x, y = y, x
prevx.next, prevy.next = x, y
temp = x.next
x.next = y.next
y.next = temp
def progress(self, first, reverse):
try:
solid = first
while first.next is not None:
if solid.data > first.next.data and not reverse:
self.swap(solid, first.next)
elif solid.data < first.next.data and reverse:
self.swap(solid, first.next)
first = first.next
except Exception:
pass
def min_sort(self, reverse):
first = self.front
while first.next is not None:
self.progress(first, reverse)
first = first.next
def min_sort(seq, reverse=False):
ll = LinkedList(seq)
ll.min_sort(reverse)
return ll.get_list()
if __name__ == '__main__':
seq = (4, 30, 8, 31, 48, 19)
lst = min_sort(seq)
print(lst)
Traceback (most recent call last):
File "/Users/rival/My files/Škola/FMFI UK/2. semester/Programovanie 2/projekt8/riesenie.py", line 66, in <module>
lst = min_sort(seq)
^^^^^^^^^^^^^
File "/Users/rival/My files/Škola/FMFI UK/2. semester/Programovanie 2/projekt8/riesenie.py", line 60, in min_sort
ll.min_sort(reverse)
File "/Users/rival/My files/Škola/FMFI UK/2. semester/Programovanie 2/projekt8/riesenie.py", line 46, in min_sort
while first.next is not None:
^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next'
I don't know how to change the reference in function min_sort so it would work
There are several issues:
The immediate cause of the error is that your swap is not happening correctly and the loop in min_sort will after two iterations and executions of progress find that first has no more next. This then leads to the error when evaluating the while condition.
The swap method does not deal well with the boundary case where the given nodes are consecutive nodes. In that case there are not four but three links to update. But as your code does not deal specifically with that case, the list gets "damaged".
Your code ignores errors that occur in progress. This is certainly not good practice. Because of how you create a list with a first node that is a dummy node, the first call of progress will try to compare None with an integer, and abort the progress execution silently.
It is not common practice to create a list with a first node that has None as data:
self.front = self.Node(None)
Although you could decide to create your list with such a dummy node that is always present, that would mean that all your methods must be aware of this special node and not ever use its data, not for comparison, not for output, not for counting, ...etc.
It is more common to not have such a dummy node permanently present in your list. You can still create a temporary dummy node, but then don't really include it in the list. On the other hand, the list constructor could insert the given values (seq) in reversed order so that you don't even need a dummy node.
swap should not have to iterate the whole list just to find the predecessor nodes. Instead make your algorithm such that it has these predecessor nodes, and then calls swap with those references.
The statement x, y = y, x has no purpose in your swap code. Although it doesn't do any harm, it doesn't do any good either where you have used it. You could just omit it.
It is strange that you sometimes swap values with tuple assignment, and sometimes with the non-pythonic use of a temp variable.
In progress you try to swap a newly found minimum node to the sorted part of the list, but you could save a few swaps by first identifying the minimum node, and only after the loop swap that one into place.
Not a problem, but it becomes a whole lot easier to debug when you implement a function that can print a linked list. For this I would suggest to make your list iterable (implementing __iter__). This can replace your get_list() method, as now you can get a list with the native list() function. Also base a __repr__ method using the fact that the linked list is iterable. Once you have that, you can print the linked list at any time, easing debugging efforts.
Here is an implementation that takes the above remarks into account:
class LinkedList:
class Node:
def __init__(self, data, nxt=None):
self.data, self.next = data, nxt
def __init__(self, seq):
self.front = None # don't insert a dummy node
for value in reversed(seq):
self.front = self.Node(value, self.front) # prepend
# Don't provide the nodes to swap, but their predecessors
def swap_after(self, prev_x, prev_y):
if prev_x == prev_y: # Nothing to do
return
x = prev_x.next
y = prev_y.next
if x == prev_y: # Boundary case
prev_x.next, x.next, y.next = y, y.next, x
elif y == prev_x: # Mirrored boundary case
prev_y.next, y.next, x.next = x, x.next, y
else: # Generic case
prev_x.next, x.next, prev_y.next, y.next = y, y.next, x, x.next
# Make the list iterable
def __iter__(self):
curr = self.front
while curr:
yield curr.data
curr = curr.next
# Provide a string representation of the list
def __repr__(self):
return "->".join(map(repr, self))
def progress(self, last_sorted, reverse):
prev_selected = prev = last_sorted
while prev.next:
if (prev.next.data > prev_selected.next.data) == reverse:
prev_selected = prev
prev = prev.next
# Swap is only needed when the final selection was made
self.swap_after(last_sorted, prev_selected)
def min_sort(self, reverse):
if not self.front:
return
dummy = self.Node(None, self.front)
last_sorted = dummy
while last_sorted.next.next:
self.progress(last_sorted, reverse)
last_sorted = last_sorted.next
self.front = dummy.next
def min_sort(seq, reverse=False):
ll = LinkedList(seq)
ll.min_sort(reverse)
return list(ll)
if __name__ == '__main__':
seq = (4, 30, 8, 31, 48, 19)
lst = min_sort(seq)
print(lst)