โปรแกรม C++ ใช้ Merge Sort กับ Linked List

เทคนิค Merge Sort ใช้หลักการแบ่งและปกครอง (divide and conquer) เราแบ่งข้อมูลทั้งหมดเป็นส่วนๆ เล็กๆ แล้วรวมกลับเป็นชิ้นใหญ่ในลำดับที่เรียงแล้ว อัลกอริทึมนี้มีประสิทธิภาพสำหรับ worst case เพราะมี time complexity ต่ำสำหรับ worst case เช่นกัน

Linked list สามารถเรียงลำดับด้วย merge-sort ได้อย่างมีประสิทธิภาพ สำหรับ linked list การรวม (merge) ง่ายมาก เราสามารถอัปเดต link เพื่อรวมได้ ในส่วนนี้เราจะดูวิธีเรียง linked list ด้วยวิธีนี้

ความซับซ้อนของเทคนิค Merge Sort

• Time Complexity - O(n log n) สำทุกกรณี

• Space Complexity - O(n)

Input - รายการไม่เรียงลำดับ: 14 20 78 98 20 45
Output - อาร์เรย์หลังเรียง: 14 20 20 45 78 98

อัลกอริทึม

mergeList(ll1, ll2)

Input: รับ linked list สองตัว ll1 และ ll2

Output: รายการที่รวมแล้ว

Begin
    ถ้า ll1 ว่าง แล้ว return ll2
    ถ้า ll2 ว่าง แล้ว return ll1
    ถ้า data(ll1) <= data(ll2) แล้ว
        new_head = ll1;
        next(new_head) = mergeList(next(ll1), ll2)
    ไม่เช่นนั้น
        new_head = ll2;
        next(new_head) = mergeList(ll1, next(ll2))
    return new_head
End

split_list(start, ll1, ll2)

Input: ตัวชี้เริ่มต้นของ linked list, สองอาร์กิวเมนต์เอาต์พุต ll1 และ ll2

Output: สอง linked list ที่สร้างจาก linked list เดิม

Begin
    slow := start
    fast := next(start)
    while fast ไม่ใช่ null ทำ
        fast := next(fast)
        ถ้า fast ไม่ใช่ null แล้ว
            slow := next(slow)
            fast := next(fast)
        จบ if
    จบ while
    ll1 := start
    ll2 := next(slow)
    next(slow) := null
End

mergeSort(start)

Input: Linked list

Output: Linked list ที่เรียงแล้ว

Begin
    head = start
    ถ้า head เป็น null หรือ next(head) เป็น null แล้ว 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 {
    // กำหนดโหนดเก็บข้อมูลและที่อยู่ next
    public:
    int data;
    node *next;
};

void display(class node* start) {
    node* p = start; // โหนดปัจจุบันเซ็ตเป็น head
    while(p != NULL) { // วนจนโหนดปัจจุบันไม่ใช่ NULL
        cout << p -> data << " ";
        p = p -> next; // ไปโหนดถัดไป
    }
}

node* getNode(int d) {
    node* temp = new node;
    temp -> data = d;
    temp -> next = NULL;
    return temp;
}

node* mergeList(node* ll1, node* ll2) {
    // ฟังก์ชันรวมสองลิสต์ที่เรียงแล้ว
    node* newhead = NULL;
    if(ll1 == NULL)
        return ll2;
    if(ll2 == NULL)
        return ll1;
    
    // รวมแบบ recursive
    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) {
    // คล้าย Floyd'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; // แยก
    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); // แยกลิสต์เป็นสองครึ่ง
    // เรียง sublist ซ้ายและขวา
    mergeSort(&ll1);
    mergeSort(&ll2);
    // รวมสองลิสต์ที่เรียงแล้ว
    *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); // สร้างลิสต์ โหนดแรก
    cin >> k;
    temp = head;
    
    while(k) {
        curr = getNode(k);
        temp -> next = curr; // เพิ่มโหนดแต่ละตัว
        temp = temp -> next;
        cin >> k;
    }
    
    cout<<"Before sorting: " << endl;
    display(head); // แสดงลิสต์
    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