Merge Sort ด้วย Multithreading ใน C++

เราได้รับอาร์เรย์จำนวนเต็มที่ไม่ได้จัดเรียง งานคือการจัดเรียงอาร์เรย์โดยใช้เทคนิค Merge Sort ที่นำไปใช้ผ่าน Multi-threading

Merge Sort

Merge Sort เป็นเทคนิคการจัดเรียงที่อิงตามเทคนิค Divide and Conquer (แบ่งและเอาชนะ) โดยเราแบ่งอาร์เรย์ออกเป็นครึ่งๆ เท่าๆ กัน แล้วนำมารวมกันในลำดับที่จัดเรียงแล้ว

อัลกอริทึมการนำ Merge Sort ไปใช้

• ตรวจสอบว่ามีสมาชิกหนึ่งตัวในรายการหรือไม่ หากมี ให้คืนค่าสมาชิกนั้น

• ถ้าไม่ใช่ ให้แบ่งข้อมูลแบบ Recursive (เรียกซ้ำ) ออกเป็นสองครึ่ง จนกว่าจะไม่สามารถแบ่งได้อีก

• สุดท้าย ให้รวมรายการย่อยๆ เข้าด้วยกันเป็นรายการใหม่ในลำดับที่จัดเรียงแล้ว

Multi-Threading (หลายเธรด)

ในระบบปฏิบัติการ Threads (เธรด) เป็นกระบวนการที่มีน้ำหนักเบา (Lightweight Process) ซึ่งรับผิดชอบในการดำเนินการส่วนหนึ่งของงาน เธรดต่างๆ แบ่งปันทรัพยากรร่วมกันเพื่อดำเนินการงานพร้อมกัน (Concurrently)

Multi-threading เป็นการนำ Multitasking ไปใช้จริง โดยที่เราสามารถรันเธรดหลายตัวบนโปรเซสเซอร์เดียว เพื่อดำเนินการงานพร้อมกัน มันแบ่งย่อยการดำเนินการเฉพาะภายในแอปพลิเคชันเดียวออกเป็นเธรดแต่ละตัว แต่ละเธรดสามารถรันแบบขนาน (Parallel) ได้

ตัวอย่าง

Input - int arr[] = {3, 2, 1, 10, 8, 5, 7, 9, 4}

Output - Sorted array is: 1, 2, 3, 4, 5, 7, 8, 9, 10

คำอธิบาย - เราได้รับอาร์เรย์ที่ไม่ได้จัดเรียงพร้อมค่าจำนวนเต็ม ตอนนี้เราจะจัดเรียงอาร์เรย์โดยใช้ Merge Sort กับ Multithreading

Input - int arr[] = {5, 3, 1, 45, 32, 21, 50}

Output - Sorted array is: 1, 3, 5, 21, 32, 45, 50

คำอธิบาย - เราได้รับอาร์เรย์ที่ไม่ได้จัดเรียงพร้อมค่าจำนวนเต็ม ตอนนี้เราจะจัดเรียงอาร์เรย์โดยใช้ Merge Sort กับ Multithreading

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• เราจะเริ่มต้นด้วยการสร้างตัวเลขสุ่มโดยใช้เมธอด rand() ใน C++ STL

• สร้างอาร์เรย์ของ pthread_t คือ P_TH[thread_size]

• เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่าขนาดเธรด ภายในลูป เรียก pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) เพื่อสร้างเธรดพร้อมค่าอาร์เรย์ที่กำหนด

• เรียกฟังก์ชัน combine_array(0, (size/2-1)/2, size/2-1), combine_array(size/2, size/2+(size-1-size/2)/2, size-1) และ combine_array(0, (size-1)/2, size-1)

• พิมพ์อาร์เรย์ที่จัดเรียงแล้วเก็บใน arr[] แบบจำนวนเต็ม

• ภายในฟังก์ชัน void* Sorting_Threading(void* arg)

  • ประกาศตัวแปร set_val เป็น temp_val++, first เป็น set_val*(size/4), end เป็น (set_val+1)*(size/4)-1 และ mid_val เป็น first+(end-first)/2

  • ตรวจสอบ IF first น้อยกว่า end แล้วเรียก Sorting_Threading(first, mid_val), Sorting_Threading(mid_val+1, end) และ combine_array(first, mid_val, end)

• ภายในฟังก์ชัน void Sorting_Threading(int first, int end)

  • ประกาศตัวแปร mid_val เป็น first+(end-first)/2

  • ตรวจสอบ IF first น้อยกว่า end แล้วเรียก Sorting_Threading(first, mid_val), Sorting_Threading(mid_val+1, end) และ combine_array(first, mid_val, end)

• ภายในฟังก์ชัน void combine_array(int first, int mid_val, int end)

  • ประกาศตัวแปร int* start = new int[mid_val-first+1], int* last = new int[end-mid_val], temp_1 = mid_val-first+1, temp_2 = end-mid_val, i, j, k = first

  • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า temp_1 ภายในลูป ตั้งค่า start[i] = arr[i+first]

  • เริ่มลูป FOR จาก i=0 ถึง i น้อยกว่า temp_2 ภายในลูป ตั้งค่า last[i] = arr[i+mid_val+1]

  • ตั้งค่า i=j=0 เริ่มลูป While i น้อยกว่า temp_1 AND j น้อยกว่า temp_2 ภายใน while ตรวจสอบ IF start[i] น้อยกว่าหรือเท่ากับ last[j] แล้วตั้งค่า arr[k++] = start[i++] มิฉะนั้น ตั้งค่า arr[k++] = last[j++]

  • เริ่ม WHILE i น้อยกว่า temp_1 แล้วตั้งค่า arr[k++] = start[i++] เริ่ม WHILE j น้อยกว่า temp_2 แล้วตั้งค่า arr[k++] = last[j++]

ตัวอย่างโค้ด

#include <iostream>
#include <pthread.h>
#include <time.h>
#define size 20
#define thread_size 4
using namespace std;

int arr[size];
int temp_val = 0;

void combine_array(int first, int mid_val, int end) {
    int* start = new int[mid_val - first + 1];
    int* last = new int[end - mid_val];
    int temp_1 = mid_val - first + 1;
    int temp_2 = end - mid_val;
    int i, j;
    int k = first;
    for(i = 0; i < temp_1; i++) {
        start[i] = arr[i + first];
    }
    for (i = 0; i < temp_2; i++) {
        last[i] = arr[i + mid_val + 1];
    }
    i = j = 0;
    while(i < temp_1 && j < temp_2) {
        if(start[i] <= last[j]) {
            arr[k++] = start[i++];
        } else {
            arr[k++] = last[j++];
        }
    }
    while (i < temp_1) {
        arr[k++] = start[i++];
    }
    while (j < temp_2) {
        arr[k++] = last[j++];
    }
}

void Sorting_Threading(int first, int end) {
    int mid_val = first + (end - first) / 2;
    if(first < end) {
        Sorting_Threading(first, mid_val);
        Sorting_Threading(mid_val + 1, end);
        combine_array(first, mid_val, end);
    }
}

void* Sorting_Threading(void* arg) {
    int set_val = temp_val++;
    int first = set_val * (size / 4);
    int end = (set_val + 1) * (size / 4) - 1;
    int mid_val = first + (end - first) / 2;
    if (first < end) {
        Sorting_Threading(first, mid_val);
        Sorting_Threading(mid_val + 1, end);
        combine_array(first, mid_val, end);
    }
}

int main() {
    for(int i = 0; i < size; i++) {
        arr[i] = rand() % 100;
    }
    pthread_t P_TH[thread_size];
    for(int i = 0; i < thread_size; i++) {
        pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL);
    }
    for(int i = 0; i < 4; i++) {
        pthread_join(P_TH[i], NULL);
    }
    combine_array(0, (size / 2 - 1) / 2, size / 2 - 1);
    combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1);
    combine_array(0, (size - 1)/2, size - 1);
    cout<<"Merge Sort using Multi-threading: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

ผลลัพธ์

หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้:

Merge Sort using Multi-threading: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93