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.
Java
// Java program for Quick Sort on
// Singly Linked List
// Sort a linked list using
// quick sort
public class QuickSortLinkedList
{
static class Node
{
int data;
Node next;
Node(int d)
{
this.data = d;
this.next = null;
}
}
Node head;
void addNode(int data)
{
if (head == null)
{
head = new Node(data);
return;
}
Node curr = head;
while (curr.next != null)
curr = curr.next;
Node newNode = new Node(data);
curr.next = newNode;
}
void printList(Node n)
{
while (n != null)
{
System.out.print(n.data);
System.out.print(" ");
n = n.next;
}
}
// Takes first and last node,
// but do not break any links in
// the whole linked list
Node partitionLast(Node start,
Node end)
{
if (start == end ||
start == null ||
end == null)
return start;
Node pivot_prev = start;
Node curr = start;
int pivot = end.data;
// Iterate till one before the end,
// no need to iterate till the end
// because end is pivot
while (start != end)
{
if (start.data < pivot)
{
// Keep tracks of last
// modified item
pivot_prev = curr;
int 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
int temp = curr.data;
curr.data = pivot;
end.data = temp;
// Return one previous to current
// because current is now pointing
// to pivot
return pivot_prev;
}
void sort(Node start, Node end)
{
if(start == null ||
start == end||
start == end.next )
return;
// Split list and partition recurse
Node pivot_prev = partitionLast(start, end);
sort(start, pivot_prev);
// If pivot is picked and moved to the start,
// that means start and pivot is same
// so pick from next of pivot
if (pivot_prev != null &&
pivot_prev == start)
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
else if (pivot_prev != null &&
pivot_prev.next != null)
sort(pivot_prev.next.next, end);
}
// Driver Code
public static void main(String[] args)
{
QuickSortLinkedList list =
new QuickSortLinkedList();
list.addNode(30);
list.addNode(3);
list.addNode(4);
list.addNode(20);
list.addNode(5);
Node n = list.head;
while (n.next != null)
n = n.next;
System.out.println(
"Linked List before sorting");
list.printList(list.head);
list.sort(list.head, n);
System.out.println(
"Linked List after sorting");
list.printList(list.head);
}
}
// This code is contributed by trinadumca
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