Вставка Сортировка с помощью связанного списка

Question

Я пытаюсь создать сортировку вставки со связанными списками. Вот что у меня есть:

def insertion_sort(a): 
     """ 
     ------------------------------------------------------- 
     Sorts a list using the Insertion Sort algorithm. 
     Use: insertion_sort(a) 
     ------------------------------------------------------- 
     Preconditions: 
      a - linked list of comparable elements (?) 
     Postconditions: 
      Contents of a are sorted. 
     ------------------------------------------------------- 
     """   
     unsorted = a._front 
     a._front = None 

     while unsorted is not None and unsorted._next is not None: 
      current = unsorted 
      unsorted = unsorted._next 

      if current._value < unsorted._value: 
       current._next = unsorted._next 
       unsorted._next = current 
       unsorted = unsorted._next 
      else: 
       find = unsorted 
       while find._next is not None and current._value > find._next._value: 
        find = find._next 

       current._next = find._next 
       current = find._next 
      a._front = unsorted 

     return a 

Я считаю, что у меня есть правильная с точки зрения сортировки. Однако, когда я пытаюсь прочитать список в основном модуле, я получаю кучу значений None.

В этом случае сортировка вставки не, создавая новый список при сортировке. Скорее, он перемещает все отсортированные элементы на «фронт».

Подводя итог, у меня есть две проблемы: я не уверен, что сортировка вставки правильная, и есть проблемы с возвращенным списком a, так как он содержит значения None. Заранее спасибо

Answer 1

Не совсем уверен в тип, но если вы предполагаете простой:

class Node: 
    def __init__(self, value, node=None): 
     self._value = value 
     self._next = node 
    def __str__(self): 
     return "Node({}, {})".format(self._value, self._next) 

Тогда ваша вставка сортировки не далеко, он должен обрабатывать случай головки правильно:

def insertion_sort(unsorted):  
    head = None 
    while unsorted: 
     current = unsorted 
     unsorted = unsorted._next 
     if not head or current._value < head._value: 
      current._next = head; 
      head = current; 
     else: 
      find = head; 
      while find and current._value > find._next._value: 
       find = find._next 
      current._next = find._next 
      find._next = current 
    return head 

>>> print(insertion_sort(Node(4, Node(1, Node(3, Node(2)))))) 
Node(1, Node(2, Node(3, Node(4, None))))