CODEWITHSUNDEEP
pythonlinked-listselection-sort
Samuel Varchol
Samuel Varchol

Reputation: 13

Selection sort for linked list by swapping nodes

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

Upvotes: 1

Views: 51

Answers (2)

trincot
trincot

Reputation: 350781

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)

Upvotes: 0

Sowmya
Sowmya

Reputation: 59

The error is because the code is trying to access the first.next for a node first which is None.

You can add try to add an additional check to handle this cases

def min_sort(self, reverse):
    first = self.front
    while first is not None and first.next is not None:
        self.progress(first, reverse)
        first = first.next

Upvotes: -1

Related Questions