Попытка быстрой сортировки связанного списка в python

Question

мой профессор попросил меня выполнить быструю сортировку для связанного списка. Это становится довольно запутанным, поскольку все рекурсии и ссылки все еще очень новы для меня. Кажется, проблема в том, что что-то непреднамеренно назначено как None. Это мой код на данный момент:

class Node:
    def __init__(self, d, n):
        self.data = d
        self.next = n


class LinkedList:

    def __init__(self):
        self.head = None
        self.length = 0

    def append(self, d):
        if self.head == None:      
            self.head = Node(d,None) 
        else:
            ptr = self.head
            while ptr.next != None:
                ptr = ptr.next
            ptr.next = Node(d,None)
        self.length += 1

    def merge(self,other):
        ptr = self.head
        while ptr.next != None:
            ptr = ptr.next
        ptr.next = other.head

    def removeVal(self, d):
        if self.head == None:
            return
        if self.head.data == d:
            self.head = self.head.next
            self.length -= 1
        else:
            ptr = self.head 
            while ptr.next != None:
                if ptr.next.data == d:
                    ptr.next = ptr.next.next
                    self.length -= 1
                    break
                ptr = ptr.next  

    def sort(self):
        if self.head!=None:
            pivot=self.head.data
            self.removeVal(pivot)
            smaller=LinkedList()
            other=LinkedList()
            ptr=self.head
            while ptr.next!=None:
                ptr=ptr.next
                if ptr.data<pivot:
                    smaller.append(ptr.data)
                else:
                    other.append(ptr.data)
            smaller.sort()
            other.sort()
            self=smaller
            self.append(pivot)
            self.merge(other)


ls = LinkedList()
ls.append(0)
ls.append(1)
ls.append(3)
ls.sort()

Выполнение этого дает следующую ошибку

Traceback (most recent call last):
  File "main.py", line 71, in <module>
    ls.sort()
  File "main.py", line 58, in sort
    other.sort()
  File "main.py", line 51, in sort
    while ptr.next!=None:
AttributeError: 'NoneType' object has no attribute 'next'

Любая помощь будет очень цениться

Answer 1

Вы не можете выполнить функцию sort (), потому что ptr может быть None, когда вы попадете в цикл while. Сначала это не очевидно из-за вашей проверки в начале

if self.head != None

Но вызов self.removeVal(pivot) установит указатель вашей головы на None, если в списке есть только 1 запись. Обратите внимание, что это всегда будет происходить во время вашей быстрой сортировки, потому что вы рекурсивно разбиваете свой список. В конце концов, он ДОЛЖЕН быть списком из 1 элемента и, следовательно, потерпеть неудачу.

Когда это происходит, вы получаете отправленную вами стековую трассировку, где написано:

AttributeError: 'NoneType' object has no attribute 'next'

Чтобы исправить это, вы можете переписать цикл whileсмотреть на ptr напрямую, а не на ptr.next

         while ptr is not None:
                if ptr.data<pivot:
                    smaller.append(ptr.data)
                else:
                    other.append(ptr.data)
                ptr=ptr.next

Еще одна проблема, которую я обнаружил, была с вашим заданием:

self=smaller

Это может быть допустимый код Python, но я нахожуэто очень опасно. Я изменил его на

self.head = smaller.head

В противном случае ваш пример удалил один элемент из списка (хотя я не отслеживал, почему именно). Обратите внимание, что это действительно не обновляет ваш атрибут длины, но я не виделзачем он нужен, он нигде не используется.

Еще одно замечание об эффективности: вы делаете много дополнений в своем алгоритме, и они ОЧЕНЬ дорого обходятся со списками, то есть способом, которым вы их реализовали. Это, вероятно, не в том, что вы здесь упражняетесь. Но когда вы добавляете итерацию по всем существующим элементам, вы убиваете эффективность быстрой сортировки. Добавление элемента стоит вам O (n) и, следовательно, разделение списка на ваш меньший и другой список уже стоит O (n ^ 2).

Для (связанных) списков сортировка слиянием - намного лучший алгоритм сортировки, которыйтакже запускает O (n * log (n)), как быстрая сортировка.

Answer 2

Как указано выше, убедитесь, что подход, показанный в вопросе, будет приемлем в качестве быстрой сортировки. Вы можете рассмотреть возможность создания 3 списков, узлов pivot, и использовать только рекурсию для 2 списка узлов! = Pivot. Добавление хвостовой ссылки в список ускорит операции добавления. Пример кода, в котором быстрая сортировка связывает узлы, чтобы переставить их, вместо того, чтобы постоянно выделять узлы.

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next=None

class Linkedlist(object):

    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def push_back(self, data):
        self.length += 1
        new = Node(data)
        if(self.tail is None):
            self.head = self.tail = new
        else:
            self.tail.next = new
            self.tail = new

    def pop_front(self):
        if(self.head is None):
            return self.head
        self.length -= 1
        data = self.head.data
        self.head = self.head.next
        return data

    def show(self, head, tail):
        arr = []
        if(head is None):
            print(arr)
            return
        while(True):
            if(head.data is not None):
                arr.append(head.data)
            if(head is tail):
                break
            head = head.next
        print(arr)

    def quicksort(self,head,tail):
        if(head is tail):               # if single node return
            return head,tail
                                        # using 3 dummy nodes for 3 lists
        hlt = Node(None)                # head, tail < pivot list
        tlt = hlt
        heq = Node(None)                # head, tail = pivot list
        teq = heq
        hgt = Node(None)                # head, tail > pivot list
        tgt = hgt
        pivot = head
        curr  = head
        end   = tail.next
        while(curr is not end):
            if(curr.data < pivot.data):
                tlt.next = curr
                tlt = curr
            elif(curr.data == pivot.data):
                teq.next = curr
                teq = curr
            else:
                tgt.next = curr
                tgt = curr
            curr = curr.next
        heq = heq.next                  # at least 1 node (should release node)
        if(hlt is tlt):                 # if none < pivot
            hlt = heq                   #  (should release dummy node)
            tlt = heq
        else:                           # else recurse on list < pivot
            hlt = hlt.next              #  (should release dummy node)
            hlt,tlt = self.quicksort(hlt,tlt)
            tlt.next = heq
        if(hgt is tgt):                 # if none > pivot
            hgt = teq                   #  (should release dummy node)
            tgt = teq
        else:                           # else recurse on list > pivot
            hgt = hgt.next              #  (should release dummy node)
            hgt,tgt = self.quicksort(hgt,tgt)
            teq.next = hgt
        return(hlt,tgt)

    def sort(self):
        if (self.head == None):         # if empty list return
            return
        self.head,self.tail = self.quicksort(self.head,self.tail)
        self.tail.next = None
        return

lists=Linkedlist()
lists.push_back(27)
lists.push_back(35)
lists.push_back(23)
lists.push_back(22)
lists.push_back(38)
lists.push_back(26)
lists.push_back(31)
lists.push_back(24)
lists.push_back(37)
lists.push_back(25)
lists.push_back(33)
lists.push_back(32)
lists.push_back(28)
lists.push_back(36)
lists.push_back(21)
lists.push_back(34)
lists.sort()
arr = []
while(True):
    data = lists.pop_front()
    if(data is None):
        break
    arr.append(data)
print(arr)

Answer 3

Внимательно прочитайте ваши коды ошибок. Там написано

File "main.py", line 51, in sort
while ptr.next!=None:
AttributeError: 'NoneType' object has no attribute 'next'

Это довольно хороший показатель того, что и где проблема. Вы получаете доступ к нулевому узлу из строки 51. Измените While ptr.next !=None на While ptr != None, и ошибка исчезнет. Вы должны выяснить, почему с помощью тестирования, хотя.