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.
Javascript
<script>
// Javascript program for Quick Sort on
// Singly LinKed List
// Sort a linked list using quick sort
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
var head;
function addNode(data)
{
if (head == null)
{
head = new Node(data);
return;
}
var curr = head;
while (curr.next != null)
curr = curr.next;
var newNode = new Node(data);
curr.next = newNode;
}
function printList(n)
{
while (n != null)
{
document.write(n.data);
document.write(" ");
n = n.next;
}
}
// Takes first and last node,
// but do not break any links in
// the whole linked list
function partitionLast(start, end)
{
if (start == end ||
start == null ||
end == null)
return start;
var pivot_prev = start;
var curr = start;
var 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;
var 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
var temp = curr.data;
curr.data = pivot;
end.data = temp;
// Return one previous to current
// because current is now pointing
// to pivot
return pivot_prev;
}
function sort(start, end)
{
if (start == null ||
start == end ||
start == end.next)
return;
// Split list and partition recurse
var 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
addNode(30);
addNode(3);
addNode(4);
addNode(20);
addNode(5);
var n = head;
while (n.next != null)
n = n.next;
document.write(
"Linked List before sorting<br/>");
printList(head);
sort(head, n);
document.write(
"<br/>Linked List after sorting<br/>");
printList(head);
// This code is contributed by umadevi9616
</script>
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