Kỹ thuật sắp xếp hợp nhất dựa trên kỹ thuật chia và chinh phục. Chúng tôi chia tập dữ liệu while thành các phần nhỏ hơn và hợp nhất chúng thành một phần lớn hơn theo thứ tự được sắp xếp. Nó cũng rất hiệu quả đối với các trường hợp xấu nhất vì thuật toán này có độ phức tạp về thời gian thấp hơn đối với trường hợp xấu nhất.
Danh sách được liên kết có thể được sắp xếp bằng cách sử dụng merge-sort rất hiệu quả. Đối với danh sách liên kết, nhiệm vụ hợp nhất rất đơn giản. Chúng tôi có thể chỉ cần cập nhật các liên kết để hợp nhất chúng. Trong phần này, chúng ta sẽ xem cách sắp xếp danh sách được liên kết bằng cách sử dụng phương pháp này.
Sự phức tạp của Kỹ thuật Sắp xếp Hợp nhất
-
Độ phức tạp về thời gian - O (n log n) cho mọi trường hợp
-
Độ phức tạp của không gian - O (n)
Input − The unsorted list: 14 20 78 98 20 45 Output − Array after Sorting: 14 20 20 45 78 98
Thuật toán
mergeList (ll1, ll2)
Đầu vào - Có hai danh sách liên kết ll1 và ll2
Đầu ra - Danh sách đã hợp nhất
Begin
if ll1 is empty, then
return ll2
if ll2 is empty, then
return ll1
if data(ll1) <= data(ll2), then
new_head = ll1;
next(new_head) = mergeList(next(ll1), ll2)
else
new_head = ll2;
next(new_head) = mergeList(ll1, next(ll2))
return new_head
End split_list (start, ll1, ll2)
Đầu vào - Con trỏ bắt đầu của một danh sách được liên kết, hai đối số đầu ra ll1 và ll2
Đầu ra - Hai danh sách liên kết được tạo từ danh sách liên kết
Begin
slow := start
fast := next(start)
while fast is not null, do
fast := next(fast)
if fast is not null, then
slow := next(slow)
fast := next(fast)
end while
ll1 := start
ll2 := next(slow)
next(slow) := null
End mergeSort (bắt đầu)
Đầu vào - Danh sách liên kết
Đầu ra - Danh sách liên kết được sắp xếp
Begin
head = start
if head is null or next(head) is null, then
return
split_list(head, ll1, ll2)
mergeSort(ll1)
mergeSort(ll2)
start := mergeList(ll1, ll2)
End Mã nguồn (C ++)
#include<bits/stdc++.h>
using namespace std;
class node { //define node to store data and next address
public:
int data;
node *next;
};
void display(class node* start) {
node* p = start; // current node set to head
while(p != NULL) { //traverse until current node isn't NULL
cout << p -> data << " ";
p = p -> next; // go to next node
}
}
node* getNode(int d) {
node* temp = new node;
temp -> data = d;
temp -> next = NULL;
return temp;
}
node* mergeList(node* ll1, node* ll2) { //function for merging two sorted list
node* newhead = NULL;
if(ll1 == NULL)
return ll2;
if(ll2 == NULL)
return ll1;
//recursively merge the lists
if(ll1 -> data <= ll2 -> data) {
newhead = ll1;
newhead -> next = mergeList(ll1->next,ll2);
} else {
newhead = ll2;
newhead -> next = mergeList(ll1,ll2->next);
}
return newhead;
}
void splitList(node* start, node** ll1,node** ll2) {
//similar to flyod's tortoise algorithm
node* slow = start;
node* fast = start -> next;
while(fast!= NULL) {
fast = fast -> next;
if(fast!= NULL) {
slow = slow -> next;
fast = fast -> next;
}
}
*ll1 = start;
*ll2 = slow -> next;
//spliting
slow -> next = NULL;
}
void mergeSort(node** start) {
node* head = *start;
node* ll1,*ll2;
//base case
if(head == NULL || head->next == NULL) {
return;
}
splitList(head,&ll1,&ll2); //split the list in two halves
//sort left and right sublists
mergeSort(&ll1);
mergeSort(&ll2);
//merge two sorted list
*start = mergeList(ll1,ll2);
return;
}
int main() {
cout << "Creating the linked list: " << endl;
cout << "Enter 0 to stop building the list, else enter any integer" << endl;
int k,count = 1,x;
node* curr,*temp;
cin >> k;
node* head = getNode(k); //buliding list, first node
cin >> k;
temp = head;
while(k) {
curr = getNode(k);
temp -> next = curr;//appending each node
temp = temp -> next;
cin >> k;
}
cout<<"Before sorting: " << endl;
display(head); // displaying the list
cout<<"\nAfter sorting: " << endl;
mergeSort(&head);
display(head);
return 0;
} Đầu ra
Creating the linked list: Enter 0 to stop building the list, else enter any integer 89 54 15 64 74 98 10 24 26 0 Before sorting: 89 54 15 64 74 98 10 24 26 After sorting: 10 15 24 26 54 64 74 89 98