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.
C++
// C++ program for Quick Sort on
// Singly Linked List
#include <cstdio>
#include <iostream>
using namespace std;
// A node of the singly
// linked list
struct Node
{
int data;
struct Node* next;
};
/* A utility function to insert a
node at the beginning of
linked list */
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node = new Node;
// Put in the data
new_node->data = new_data;
// Link the old list off the
// new node
new_node->next = (*head_ref);
// Move the head to point to
// the new node
(*head_ref) = new_node;
}
// A utility function to print
// linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("");
}
// Returns the last node of the list
struct Node* getTail(struct Node* cur)
{
while (cur != NULL &&
cur->next != NULL)
cur = cur->next;
return cur;
}
// Partitions the list taking the
// last element as the pivot
struct Node* partition(struct Node* head,
struct Node* end,
struct Node** newHead,
struct Node** newEnd)
{
struct Node* pivot = end;
struct Node *prev = NULL,
*cur = head, *tail = pivot;
// During partition, both the head and
// end of the list might change which
// is updated in the newHead and newEnd
// variables
while (cur != pivot)
{
if (cur->data < pivot->data)
{
// First node that has a value
// less than the pivot - becomes
// the new head
if ((*newHead) == NULL)
(*newHead) = cur;
prev = cur;
cur = cur->next;
}
// If cur node is greater than pivot
else
{
// Move cur node to next of tail,
// and change tail
if (prev)
prev->next = cur->next;
struct Node* tmp = cur->next;
cur->next = NULL;
tail->next = cur;
tail = cur;
cur = tmp;
}
}
// If the pivot data is the smallest element
// in the current list, pivot becomes the head
if ((*newHead) == NULL)
(*newHead) = pivot;
// Update newEnd to the current last node
(*newEnd) = tail;
// Return the pivot node
return pivot;
}
// here the sorting happens exclusive of the
// end node
struct Node* quickSortRecur(struct Node* head,
struct Node* end)
{
// Base condition
if (!head || head == end)
return head;
Node *newHead = NULL, *newEnd = NULL;
// Partition the list, newHead and newEnd
// will be updated by the partition function
struct Node* pivot = partition(head, end,
&newHead, &newEnd);
// If pivot is the smallest element - no need
// to recur for the left part.
if (newHead != pivot)
{
// Set the node before the pivot node
// as NULL
struct Node* tmp = newHead;
while (tmp->next != pivot)
tmp = tmp->next;
tmp->next = NULL;
// Recur for the list before pivot
newHead = quickSortRecur(newHead, tmp);
// Change next of last node of the
// left half to pivot
tmp = getTail(newHead);
tmp->next = pivot;
}
// Recur for the list after the
// pivot element
pivot->next = quickSortRecur(pivot->next,
newEnd);
return newHead;
}
// The main function for quick sort.
// This is a wrapper over recursive
// function quickSortRecur()
void quickSort(struct Node** headRef)
{
(*headRef) = quickSortRecur(*headRef,
getTail(*headRef));
return;
}
// Driver code
int main()
{
struct Node* a = NULL;
push(&a, 5);
push(&a, 20);
push(&a, 4);
push(&a, 3);
push(&a, 30);
cout << "Linked List before sorting ";
printList(a);
quickSort(&a);
cout << "Linked List after sorting ";
printList(a);
return 0;
}
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