Tri de l'insertion avec une liste chaînée

Question

J'essaie de créer un tri d'insertion avec des listes liées. Voici ce que j'ai:

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 

Je crois que ce que j'ai est correct en termes de tri. Cependant quand j'essaye de lire la liste dans le module principal j'obtiens un tas de valeurs None.

Dans ce cas, le tri par insertion est et non en créant une nouvelle liste lors du tri. Au contraire, il déplace tous les éléments triés vers le «front».

Pour résumer, j'ai deux problèmes: Je ne suis pas sûr si le tri d'insertion est correct, et il y a des problèmes avec la liste retournée a car il contient None valeurs. Merci à l'avance

Answer 1

Pas exactement sûr du type d'un est, mais si vous assumez simple:

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

Ensuite, votre type d'insertion est pas loin, il faut traiter le cas de la tête correctement:

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))))