ผสานการเรียงลำดับโดยใช้มัลติเธรดใน C ++

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

ผสานการเรียงลำดับ

Merge sort เป็นเทคนิคการจัดเรียงตามเทคนิคการหารและพิชิต โดยที่เราแบ่งอาร์เรย์ออกเป็นครึ่งหนึ่งเท่าๆ กัน แล้วรวมเข้าด้วยกันในลักษณะที่จัดเรียง

อัลกอริธึมในการใช้งานการเรียงลำดับการผสานคือ

• ตรวจสอบว่ามีองค์ประกอบอยู่ในรายการแล้วส่งคืนองค์ประกอบหรือไม่

• มิฉะนั้น ให้แบ่งข้อมูลซ้ำเป็นสองส่วนจนกว่าจะแบ่งไม่ได้

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

มัลติเธรดดิ้ง

ในระบบปฏิบัติการ กระทู้ เป็นกระบวนการที่มีน้ำหนักเบาซึ่งมีหน้าที่ในการดำเนินการในส่วนของงาน เธรดแบ่งปันทรัพยากรร่วมกันเพื่อดำเนินงานพร้อมกัน

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

ตัวอย่าง-:

ใน −int arr[] ={3, 2, 1, 10, 8, 5, 7, 9, 4}

ออก −เรียงลำดับอาร์เรย์คือ:1, 2, 3, 4, 5, 7, 8, 9, 10

คำอธิบาย −เราได้รับอาร์เรย์ที่ไม่เรียงลำดับที่มีค่าจำนวนเต็ม ตอนนี้เราจะจัดเรียงอาร์เรย์โดยใช้การเรียงลำดับผสานกับมัลติเธรด

ใน −int arr[] ={5, 3, 1, 45, 32, 21, 50}

ออก −เรียงลำดับอาร์เรย์คือ:1, 3, 5, 21, 32, 45, 50

คำอธิบาย −เราได้รับอาร์เรย์ที่ไม่เรียงลำดับที่มีค่าจำนวนเต็ม ตอนนี้เราจะจัดเรียงอาร์เรย์โดยใช้การเรียงลำดับผสานกับมัลติเธรด

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

• เราจะเริ่มต้นด้วยการสร้างตัวเลขสุ่มโดยใช้วิธี 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, (ขนาด / 2 - 1) / 2, ขนาด / 2 - 1), combine_array(ขนาด / 2, ขนาด/2 + (ขนาด-1-ขนาด/2)/2, ขนาด - 1) และ combine_array(0, (ขนาด - 1)/2, ขนาด - 1)

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

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

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

  • ตรวจสอบว่า IF น้อยกว่า 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 น้อยกว่า 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* เริ่มต้นเป็น int ใหม่[mid_val - first + 1], int* อยู่หลัง int ใหม่[end - mid_val], temp_1 ถึง mid_val - แรก + 1, temp_2 ถึงสิ้นสุด - mid_val, i, j, k เป็นอันดับแรก .

  • เริ่มวนซ้ำ 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 เริ่มวนรอบ ขณะที่ i น้อยกว่า temp_1 และ j น้อยกว่า temp_2 ในระหว่างนี้ ให้ตรวจสอบ IF start[i] less than last[j] จากนั้นตั้งค่า arr[k++] เป็น start[i++] มิฉะนั้น ให้ตั้งค่า arr[k++] =สุดท้าย[j++]

  • เริ่มในขณะที่ฉันน้อยกว่า temp_1 จากนั้นตั้งค่า arr[k++] =start[i++] เริ่มในขณะที่ j น้อยกว่า temp_2 จากนั้นตั้งค่า arr[k++] เป็น [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