Programa Python para QuickSort en una lista enlazada individualmente

QuickSort en la lista doblemente enlazada se analiza aquí . QuickSort en una lista enlazada individualmente se proporcionó como ejercicio. Las cosas importantes acerca de la implementación son que cambia los punteros en lugar de intercambiar datos y la complejidad del tiempo es la misma que la implementación de la lista doblemente enlazada.

sorting image

En la partición() , consideramos el último elemento como pivote. Recorremos la lista actual y si un Node tiene un valor mayor que el pivote, lo movemos después de la cola. Si el Node tiene un valor menor, lo mantenemos en su posición actual.

En QuickSortRecur() , primero llamamos a la partición() que coloca el pivote en la posición correcta y devuelve el pivote. Después de colocar el pivote en la posición correcta, encontramos el Node de cola del lado izquierdo (lista antes del pivote) y recurrimos a la lista izquierda. Finalmente, recurrimos a la lista derecha.

Python3

# Sort a linked list using quick sort
class Node:
    def __init__(self, val):
        self.data = val
        self.next = None
  
class QuickSortLinkedList:
    def __init__(self):
        self.head=None
  
    def addNode(self, data):
        if (self.head == None):
            self.head = Node(data)
            return
  
        curr = self.head
        while (curr.next != None):
            curr = curr.next
  
        newNode = Node(data)
        curr.next = newNode
  
    def printList(self, n):
        while (n != None):
            print(n.data, end = " ")
            n = n.next
  
    ''' Takes first and last node,but do not
        break any links in the whole linked list'''
    def partitionLast(self, start, end):
        if (start == end or 
            start == None or end == None):
            return start
  
        pivot_prev = start
        curr = start
        pivot = end.data
  
        ''' Iterate till one before the end, 
            no need to iterate till the end 
            because the end is pivot '''
        while (start != end):
            if (start.data < pivot):
                
                # Keep tracks of last 
                # modified item
                pivot_prev = curr
                temp = curr.data
                curr.data = start.data
                start.data = temp
                curr = curr.next
            start = start.next
  
        ''' Swap the position of curr i.e. 
            next suitable index and pivot'''
        temp = curr.data
        curr.data = pivot
        end.data = temp
  
        ''' Return one previous to current 
            because current is now pointing 
            to pivot '''
        return pivot_prev
  
    def sort(self, start, end):
        if(start == None or 
           start == end or start == end.next):
            return
  
        # Split list and partition recurse
        pivot_prev = self.partitionLast(start, 
                                       end)
        self.sort(start, pivot_prev)
  
        ''' If pivot is picked and moved to 
            the start, that means start and 
            pivot is the same so pick from 
            next of pivot '''
        if(pivot_prev != None and 
           pivot_prev == start):
            self.sort(pivot_prev.next, end)
  
        # If pivot is in between of the list, 
        # start from next of pivot, since we 
        # have pivot_prev, so we move two nodes
        elif (pivot_prev != None and 
              pivot_prev.next != None):
            self.sort(pivot_prev.next.next, 
                      end)
  
# Driver code
if __name__ == "__main__":
    ll = QuickSortLinkedList()
    ll.addNode(30)
    ll.addNode(3)
    ll.addNode(4)
    ll.addNode(20)
    ll.addNode(5)
  
    n = ll.head
    while (n.next != None):
        n = n.next
  
    print("Linked List before sorting")
    ll.printList(ll.head)
  
    ll.sort(ll.head, n)
  
    print("Linked List after sorting");
    ll.printList(ll.head)
# This code is contributed by humpheykibet

Producción:

Linked List before sorting 
30 3 4 20 5 
Linked List after sorting 
3 4 5 20 30 

¡ Consulte el artículo completo sobre QuickSort en la lista de enlaces individuales para obtener más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *