A menudo se prefiere la ordenación por combinación para ordenar una lista vinculada. El lento rendimiento de acceso aleatorio de una lista enlazada hace que algunos otros algoritmos (como la ordenación rápida) funcionen mal y otros (como la ordenación heap) sean completamente imposibles.
Deje que head sea el primer Node de la lista enlazada que se ordenará y headRef sea el puntero a head. Tenga en cuenta que necesitamos una referencia al encabezado en MergeSort() ya que la implementación a continuación cambia los siguientes enlaces para ordenar las listas vinculadas (no los datos en los Nodes), por lo que el Node principal debe cambiarse si los datos en el encabezado original no son los valor más pequeño en la lista enlazada.
MergeSort(headRef)
1) If head is NULL or there is only one element in the Linked List
then return.
2) Else divide the linked list into two halves.
FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
MergeSort(a);
MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here)
and update the head pointer using headRef.
*headRef = SortedMerge(a, b);
C
// C code for linked list merged sort
#include <stdio.h>
#include <stdlib.h>
// Link list node
struct Node
{
int data;
struct Node* next;
};
// Function prototypes
struct Node* SortedMerge(struct Node* a,
struct Node* b);
void FrontBackSplit(struct Node* source,
struct Node** frontRef,
struct Node** backRef);
// Sorts the linked list by changing
// next pointers (not data)
void MergeSort(struct Node** headRef)
{
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
// Base case -- length 0 or 1
if ((head == NULL) ||
(head->next == NULL))
{
return;
}
// Split head into 'a' and 'b' sublists
FrontBackSplit(head, &a, &b);
// Recursively sort the sublists
MergeSort(&a);
MergeSort(&b);
/* answer = merge the two sorted
lists together */
*headRef = SortedMerge(a, b);
}
/* See https:// www.geeksforgeeks.org/?p=3622
for details of this function */
struct Node* SortedMerge(struct Node* a,
struct Node* b)
{
struct Node* result = NULL;
// Base cases
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
// Pick either a or b, and recur
if (a->data <= b->data)
{
result = a;
result->next =
SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return (result);
}
// UTILITY FUNCTIONS
/* Split the nodes of the given list into
front and back halves, and return the
two lists using the reference parameters.
If the length is odd, the extra node should
go in the front list.Uses the fast/slow
pointer strategy. */
void FrontBackSplit(struct Node* source,
struct Node** frontRef,
struct Node** backRef)
{
struct Node* fast;
struct Node* slow;
slow = source;
fast = source->next;
/* Advance 'fast' two nodes, and
advance 'slow' one node */
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
/* 'slow' is before the midpoint in the
list, so split it in two at that point. */
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
/* Function to print nodes in a given
linked list */
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Function to insert a node at the
beginning of the linked list */
void push(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct 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;
}
// Driver code
int main()
{
// Start with the empty list
struct Node* res = NULL;
struct Node* a = NULL;
/* Let us create a unsorted linked lists
to test the functions created lists shall
be a: 2->3->20->5->10->15 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&a, 20);
push(&a, 3);
push(&a, 2);
// Sort the above created Linked List
MergeSort(&a);
printf("Sorted Linked List is: \n");
printList(a);
getchar();
return 0;
}
Producción:
Sorted Linked List is: 2 3 5 10 15 20
Complejidad de tiempo: O(n*log n)
Complejidad espacial: O(n*log n)
¡ Consulte el artículo completo sobre Merge Sort para listas vinculadas 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