Dada una lista de números enteros enlazada individualmente, la tarea es clasificarla utilizando la clasificación por combinación iterativa.
Merge Sort a menudo se prefiere para ordenar una lista vinculada. Se discute aquí . Sin embargo, el método discutido anteriormente usa Stack para almacenar llamadas recursivas. Esto puede consumir mucha memoria si la lista vinculada que se ordenará es demasiado grande. Por lo tanto, en esta publicación se analiza un método puramente iterativo para Merge Sort sin llamadas recursivas.
Usamos el enfoque de abajo hacia arriba de Merge Sort en esta publicación. Sabemos que Merge Sort primero combina dos elementos, luego 4 elementos y así sucesivamente. La idea es usar una variable entera para almacenar la brecha para encontrar el punto medio alrededor del cual se debe ordenar la lista vinculada. Entonces, el problema se reduce a la fusión de dos listas enlazadas ordenadas que se analizan aquí. Sin embargo, no usamos una lista adicional para mantener la lista fusionada. En su lugar, fusionamos las listas dentro de sí mismo. La brecha se incrementa exponencialmente en 2 en cada iteración y el proceso se repite.
C++
// Iterative C++ program to do merge sort on
// linked list
#include <iostream>
using namespace std;
/* Structure of the Node */
struct Node {
int data;
struct Node* next;
};
/* Function to calculate length of linked list */
int length(struct Node* current)
{
int count = 0;
while (current != NULL) {
current = current->next;
count++;
}
return count;
}
/* Merge function of Merge Sort to Merge the two sorted parts
of the Linked List. We compare the next value of start1 and
current value of start2 and insert start2 after start1 if
it's smaller than next value of start1. We do this until
start1 or start2 end. If start1 ends, then we assign next
of start1 to start2 because start2 may have some elements
left out which are greater than the last value of start1.
If start2 ends then we assign end2 to end1. This is necessary
because we use end2 in another function (mergeSort function)
to determine the next start1 (i.e) start1 for next
iteration = end2->next */
void merge(struct Node** start1, struct Node** end1,
struct Node** start2, struct Node** end2)
{
// Making sure that first node of second
// list is higher.
struct Node* temp = NULL;
if ((*start1)->data > (*start2)->data) {
swap(*start1, *start2);
swap(*end1, *end2);
}
// Merging remaining nodes
struct Node* astart = *start1, *aend = *end1;
struct Node* bstart = *start2, *bend = *end2;
struct Node* bendnext = (*end2)->next;
while (astart != aend && bstart != bendnext) {
if (astart->next->data > bstart->data) {
temp = bstart->next;
bstart->next = astart->next;
astart->next = bstart;
bstart = temp;
}
astart = astart->next;
}
if (astart == aend)
astart->next = bstart;
else
*end2 = *end1;
}
/* MergeSort of Linked List
The gap is initially 1. It is incremented as
2, 4, 8, .. until it reaches the length of the
linked list. For each gap, the linked list is
sorted around the gap.
The prevend stores the address of the last node after
sorting a part of linked list so that it's next node
can be assigned after sorting the succeeding list.
temp is used to store the next start1 because after
sorting, the last node will be different. So it
is necessary to store the address of start1 before
sorting. We select the start1, end1, start2, end2 for
sorting. start1 - end1 may be considered as a list
and start2 - end2 may be considered as another list
and we are merging these two sorted list in merge
function and assigning the starting address to the
previous end address. */
void mergeSort(struct Node** head)
{
if (*head == NULL)
return;
struct Node* start1 = NULL, *end1 = NULL;
struct Node* start2 = NULL, *end2 = NULL;
struct Node* prevend = NULL;
int len = length(*head);
for (int gap = 1; gap < len; gap = gap*2) {
start1 = *head;
while (start1) {
// If this is first iteration
bool isFirstIter = 0;
if (start1 == *head)
isFirstIter = 1;
// First part for merging
int counter = gap;
end1 = start1;
while (--counter && end1->next)
end1 = end1->next;
// Second part for merging
start2 = end1->next;
if (!start2)
break;
counter = gap;
end2 = start2;
while (--counter && end2->next)
end2 = end2->next;
// To store for next iteration.
Node *temp = end2->next;
// Merging two parts.
merge(&start1, &end1, &start2, &end2);
// Update head for first iteration, else
// append after previous list
if (isFirstIter)
*head = start1;
else
prevend->next = start1;
prevend = end2;
start1 = temp;
}
prevend->next = start1;
}
}
/* Function to print the Linked List */
void print(struct Node** head)
{
if ((*head) == NULL)
return;
struct Node* temp = *head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
/* Given a reference (pointer to
pointer) to the head of a list
and an int, push a new node on
the front of the list. */
void push(struct Node** head_ref,
int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
// start with empty list
struct Node* head = NULL;
// create linked list
// 1->2->3->4->5->6->7
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
mergeSort(&head);
print(&head);
}
Java
// Iterative Java program to do merge sort on
// linked list
class GFG
{
/* Structure of the Node */
static class Node
{
int data;
Node next;
};
/* Function to calculate length of linked list */
static int length(Node current)
{
int count = 0;
while (current != null)
{
current = current.next;
count++;
}
return count;
}
/* Merge function of Merge Sort to Merge the two sorted parts
of the Linked List. We compare the next value of start1 and
current value of start2 and insert start2 after start1 if
it's smaller than next value of start1. We do this until
start1 or start2 end. If start1 ends, then we assign next
of start1 to start2 because start2 may have some elements
left out which are greater than the last value of start1.
If start2 ends then we assign end2 to end1. This is necessary
because we use end2 in another function (mergeSort function)
to determine the next start1 (i.e) start1 for next
iteration = end2.next */
static Node merge(Node start1, Node end1,
Node start2, Node end2)
{
// Making sure that first node of second
// list is higher.
Node temp = null;
if ((start1).data > (start2).data)
{
Node t = start1;
start1 = start2;
start2 = t;
t = end1;
end1 = end2;
end2 = t;
}
// Merging remaining nodes
Node astart = start1, aend = end1;
Node bstart = start2, bend = end2;
Node bendnext = (end2).next;
while (astart != aend && bstart != bendnext)
{
if (astart.next.data > bstart.data)
{
temp = bstart.next;
bstart.next = astart.next;
astart.next = bstart;
bstart = temp;
}
astart = astart.next;
}
if (astart == aend)
astart.next = bstart;
else
end2 = end1;
return start1;
}
/* MergeSort of Linked List
The gap is initially 1. It is incremented as
2, 4, 8, .. until it reaches the length of the
linked list. For each gap, the linked list is
sorted around the gap.
The prevend stores the address of the last node after
sorting a part of linked list so that it's next node
can be assigned after sorting the succeeding list.
temp is used to store the next start1 because after
sorting, the last node will be different. So it
is necessary to store the address of start1 before
sorting. We select the start1, end1, start2, end2 for
sorting. start1 - end1 may be considered as a list
and start2 - end2 may be considered as another list
and we are merging these two sorted list in merge
function and assigning the starting address to the
previous end address. */
static Node mergeSort(Node head)
{
if (head == null)
return head;
Node start1 = null, end1 = null;
Node start2 = null, end2 = null;
Node prevend = null;
int len = length(head);
for (int gap = 1; gap < len; gap = gap*2)
{
start1 = head;
while (start1 != null)
{
// If this is first iteration
boolean isFirstIter = false;
if (start1 == head)
isFirstIter = true;
// First part for merging
int counter = gap;
end1 = start1;
while (--counter > 0 && end1.next != null)
end1 = end1.next;
// Second part for merging
start2 = end1.next;
if (start2 == null)
break;
counter = gap;
end2 = start2;
while (--counter > 0 && end2.next != null)
end2 = end2.next;
// To store for next iteration.
Node temp = end2.next;
// Merging two parts.
merge(start1, end1, start2, end2);
// Update head for first iteration, else
// append after previous list
if (isFirstIter)
head = start1;
else
prevend.next = start1;
prevend = end2;
start1 = temp;
}
prevend.next = start1;
}
return head;
}
/* Function to print the Linked List */
static void print(Node head)
{
if ((head) == null)
return;
Node temp = head;
while (temp != null)
{
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("\n");
}
/* Given a reference (pointer to
pointer) to the head of a list
and an int, push a new node on
the front of the list. */
static Node push( Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
public static void main(String args[])
{
// start with empty list
Node head = null;
// create linked list
// 1.2.3.4.5.6.7
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
head = mergeSort(head);
print(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Iterative Python3 program to do merge sort on # linked list class Node: """Structure of the Node.""" def __init__(self, data: int): self.data = data self.next = None class LinkedList: """Encapsulate each left/right part's nodes in order to pass them as pointers. Without this workaround, the code would only work for a reverse-ordered list.""" head: Node tail: Node def __init__(self, head=None, tail=None): self.start = head self.end = tail def list_length(current: Node): """Function to calculate length of linked list.""" count = 0; while (current != None): current = current.next; count += 1 return count; def merge(left: LinkedList, right: LinkedList) -> None: """Merge the two sorted parts of the original linked list in order. Merge function of Merge Sort to Merge the two sorted parts of the Linked List. We compare the next value of start1 and current value of start2 and insert start2 after start1 if it's smaller than next value of start1. We do this until start1 or start2 end. If start1 ends, then we assign next of start1 to start2 because start2 may have some elements left out which are greater than the last value of start1. If start2 ends then we assign end2 to end1. This is necessary because we use end2 in another function (mergeSort function) to determine the next start1 (i.e) start1 for next iteration = end2.next""" # Ensure the first node of the second list is higher. if left.start.data > right.start.data: left.start, right.start = right.start, left.start left.end, right.end = right.end, left.end # Merge all remaining nodes. astart = left.start aend = left.end bstart = right.start bendnext = right.end.next while astart != aend and bstart != bendnext: if astart.next.data > bstart.data: temp = bstart.next bstart.next = astart.next astart.next = bstart bstart = temp astart = astart.next if astart == aend: astart.next = bstart else: right.end = left.end def mergeSort(head: LinkedList) -> None: """MergeSort of Linked List The gap is initially 1. It is incremented as 2, 4, 8, .. until it reaches the length of the linked list. For each gap, the linked list is sorted around the gap. The prevend stores the address of the last node after sorting a part of linked list so that it's next node can be assigned after sorting the succeeding list. temp is used to store the next start1 because after sorting, the last node will be different. So it is necessary to store the address of start1 before sorting. We select the start1, end1, start2, end2 for sorting. start1 - end1 may be considered as a list and start2 - end2 may be considered as another list and we are merging these two sorted list in merge function and assigning the starting address to the previous end address.""" # Reject empty lists. if not head: return gap = 1 length = list_length(head.start) left = LinkedList() right = LinkedList() while gap < length: left.start = head.start while left.start: # If this is first iteration isFirstIter = False if left.start == head.start: isFirstIter = True # First part for merging counter = gap left.end = left.start counter -= 1 while counter != 0 and left.end.next: counter -= 1 left.end = left.end.next # Second part for merging right.start = left.end.next if not right.start: break counter = gap right.end = right.start counter -= 1 while counter != 0 and right.end.next: counter -= 1 right.end = right.end.next # To store for next iteration. temp = right.end.next # Merging two parts. merge(left, right) # Update head for first iteration, else append after previous list. if isFirstIter: head.start = left.start else: prevend.next = left.start prevend = right.end left.start = temp gap = gap * 2 prevend.next = left.start def prints(head): """Print the linked list.""" if not head: return temp = head while temp: print(temp.data, end=' ') temp = temp.next print() def push(head: LinkedList, data: int) -> None: """Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list.""" new_node = Node(data) new_node.next = head.start head.start = new_node # Driver code if __name__=='__main__': # start with empty list head = LinkedList() # create linked list # 1.2.3.4.5.6.7 push(head, 6) push(head, 7) push(head, 2) push(head, 1) push(head, 3) push(head, 5) push(head, 4) mergeSort(head) prints(head.start) # This code is contributed by har2 (har-at-usf)
C#
// Iterative C# program to do merge sort on
// linked list
using System;
class GFG
{
/* Structure of the Node */
public class Node
{
public int data;
public Node next;
};
/* Function to calculate length of linked list */
static int length(Node current)
{
int count = 0;
while (current != null)
{
current = current.next;
count++;
}
return count;
}
/* Merge function of Merge Sort to Merge the two sorted parts
of the Linked List. We compare the next value of start1 and
current value of start2 and insert start2 after start1 if
it's smaller than next value of start1. We do this until
start1 or start2 end. If start1 ends, then we assign next
of start1 to start2 because start2 may have some elements
left out which are greater than the last value of start1.
If start2 ends then we assign end2 to end1. This is necessary
because we use end2 in another function (mergeSort function)
to determine the next start1 (i.e) start1 for next
iteration = end2.next */
static Node merge(Node start1, Node end1,
Node start2, Node end2)
{
// Making sure that first node of second
// list is higher.
Node temp = null;
if ((start1).data > (start2).data)
{
Node t = start1;
start1 = start2;
start2 = t;
t = end1;
end1 = end2;
end2 = t;
}
// Merging remaining nodes
Node astart = start1, aend = end1;
Node bstart = start2, bend = end2;
Node bendnext = (end2).next;
while (astart != aend && bstart != bendnext)
{
if (astart.next.data > bstart.data)
{
temp = bstart.next;
bstart.next = astart.next;
astart.next = bstart;
bstart = temp;
}
astart = astart.next;
}
if (astart == aend)
astart.next = bstart;
else
end2 = end1;
return start1;
}
/* MergeSort of Linked List
The gap is initially 1. It is incremented as
2, 4, 8, .. until it reaches the length of the
linked list. For each gap, the linked list is
sorted around the gap.
The prevend stores the address of the last node after
sorting a part of linked list so that it's next node
can be assigned after sorting the succeeding list.
temp is used to store the next start1 because after
sorting, the last node will be different. So it
is necessary to store the address of start1 before
sorting. We select the start1, end1, start2, end2 for
sorting. start1 - end1 may be considered as a list
and start2 - end2 may be considered as another list
and we are merging these two sorted list in merge
function and assigning the starting address to the
previous end address. */
static Node mergeSort(Node head)
{
if (head == null)
return head;
Node start1 = null, end1 = null;
Node start2 = null, end2 = null;
Node prevend = null;
int len = length(head);
for (int gap = 1; gap < len; gap = gap*2)
{
start1 = head;
while (start1 != null)
{
// If this is first iteration
Boolean isFirstIter = false;
if (start1 == head)
isFirstIter = true;
// First part for merging
int counter = gap;
end1 = start1;
while (--counter > 0 && end1.next != null)
end1 = end1.next;
// Second part for merging
start2 = end1.next;
if (start2 == null)
break;
counter = gap;
end2 = start2;
while (--counter > 0 && end2.next != null)
end2 = end2.next;
// To store for next iteration.
Node temp = end2.next;
// Merging two parts.
merge(start1, end1, start2, end2);
// Update head for first iteration, else
// append after previous list
if (isFirstIter)
head = start1;
else
prevend.next = start1;
prevend = end2;
start1 = temp;
}
prevend.next = start1;
}
return head;
}
/* Function to print the Linked List */
static void print(Node head)
{
if ((head) == null)
return;
Node temp = head;
while (temp != null)
{
Console.Write( temp.data + " ");
temp = temp.next;
}
Console.Write("\n");
}
/* Given a reference (pointer to
pointer) to the head of a list
and an int, push a new node on
the front of the list. */
static Node push( Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Driver code
public static void Main(String []args)
{
// start with empty list
Node head = null;
// create linked list
// 1.2.3.4.5.6.7
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
head = mergeSort(head);
print(head);
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// Iterative JavaScript program to do merge sort on
// linked list
/* Structure of the Node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/* Function to calculate length of linked list */
function length(current) {
var count = 0;
while (current != null) {
current = current.next;
count++;
}
return count;
}
/* Merge function of Merge Sort to Merge the two sorted parts
of the Linked List. We compare the next value of start1 and
current value of start2 and insert start2 after start1 if
it's smaller than next value of start1. We do this until
start1 or start2 end. If start1 ends, then we assign next
of start1 to start2 because start2 may have some elements
left out which are greater than the last value of start1.
If start2 ends then we assign end2 to end1. This is necessary
because we use end2 in another function (mergeSort function)
to determine the next start1 (i.e) start1 for next
iteration = end2.next */
function merge(start1, end1, start2, end2) {
// Making sure that first node of second
// list is higher.
var temp = null;
if (start1.data > start2.data) {
var t = start1;
start1 = start2;
start2 = t;
t = end1;
end1 = end2;
end2 = t;
}
// Merging remaining nodes
var astart = start1,
aend = end1;
var bstart = start2,
bend = end2;
var bendnext = end2.next;
while (astart != aend && bstart != bendnext) {
if (astart.next.data > bstart.data) {
temp = bstart.next;
bstart.next = astart.next;
astart.next = bstart;
bstart = temp;
}
astart = astart.next;
}
if (astart == aend) astart.next = bstart;
else end2 = end1;
return start1;
}
/* MergeSort of Linked List
The gap is initially 1. It is incremented as
2, 4, 8, .. until it reaches the length of the
linked list. For each gap, the linked list is
sorted around the gap.
The prevend stores the address of the last node after
sorting a part of linked list so that it's next node
can be assigned after sorting the succeeding list.
temp is used to store the next start1 because after
sorting, the last node will be different. So it
is necessary to store the address of start1 before
sorting. We select the start1, end1, start2, end2 for
sorting. start1 - end1 may be considered as a list
and start2 - end2 may be considered as another list
and we are merging these two sorted list in merge
function and assigning the starting address to the
previous end address. */
function mergeSort(head) {
if (head == null) return head;
var start1 = null,
end1 = null;
var start2 = null,
end2 = null;
var prevend = null;
var len = length(head);
for (var gap = 1; gap < len; gap = gap * 2) {
start1 = head;
while (start1 != null) {
// If this is first iteration
var isFirstIter = false;
if (start1 == head) isFirstIter = true;
// First part for merging
var counter = gap;
end1 = start1;
while (--counter > 0 && end1.next != null)
end1 = end1.next;
// Second part for merging
start2 = end1.next;
if (start2 == null) break;
counter = gap;
end2 = start2;
while (--counter > 0 && end2.next != null)
end2 = end2.next;
// To store for next iteration.
var temp = end2.next;
// Merging two parts.
merge(start1, end1, start2, end2);
// Update head for first iteration, else
// append after previous list
if (isFirstIter) head = start1;
else prevend.next = start1;
prevend = end2;
start1 = temp;
}
prevend.next = start1;
}
return head;
}
/* Function to print the Linked List */
function print(head) {
if (head == null) return;
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br>");
}
/* Given a reference (pointer to
pointer) to the head of a list
and an int, push a new node on
the front of the list. */
function push(head_ref, new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
// Driver code
// start with empty list
var head = null;
// create linked list
// 1.2.3.4.5.6.7
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
head = mergeSort(head);
print(head);
</script>
Producción
1 2 3 4 5 6 7
Complejidad de Tiempo : O(n Log n)
Espacio Auxiliar : O(1)