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