เทคนิคการจัดเรียงแบบผสานจะขึ้นอยู่กับเทคนิคการแบ่งและพิชิต เราแบ่งชุดข้อมูล while ออกเป็นส่วนเล็กๆ และรวมเข้าด้วยกันเป็นชิ้นที่ใหญ่ขึ้นตามลำดับ นอกจากนี้ยังมีประสิทธิภาพมากสำหรับกรณีที่เลวร้ายที่สุดเพราะอัลกอริธึมนี้มีเวลาน้อยกว่าสำหรับกรณีที่เลวร้ายที่สุดเช่นกัน
รายการที่เชื่อมโยงสามารถเรียงลำดับได้โดยใช้การผสานการเรียงลำดับอย่างมีประสิทธิภาพมาก สำหรับรายการที่เชื่อมโยง งานการผสานนั้นง่ายมาก เราสามารถอัปเดตลิงก์เพื่อรวมเข้าด้วยกันได้ ในส่วนนี้เราจะมาดูวิธีการจัดเรียงรายการที่เชื่อมโยงโดยใช้วิธีนี้
ความซับซ้อนของเทคนิคการจัดเรียงแบบผสาน
-
ความซับซ้อนของเวลา − O(n log n) ทุกกรณี
-
ความซับซ้อนของอวกาศ − O(n)
Input − The unsorted list: 14 20 78 98 20 45 Output − Array after Sorting: 14 20 20 45 78 98
อัลกอริทึม
mergeList(ll1, ll2)
ป้อนข้อมูล − ต้องใช้สองรายการที่เชื่อมโยง ll1 และ ll2
ผลผลิต − รายการรวม
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)
ป้อนข้อมูล − ตัวชี้เริ่มต้นของรายการที่เชื่อมโยง สองอาร์กิวเมนต์เอาต์พุต ll1 และ ll2
ผลผลิต − รายการเชื่อมโยงสองรายการที่สร้างจากรายการที่เชื่อมโยง
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(เริ่ม)
ป้อนข้อมูล − รายการเชื่อมโยง
ผลผลิต − เรียงลำดับลิงค์ลิสต์
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 ซอร์สโค้ด (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;
} ผลลัพธ์
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
