Hợp nhất Sắp xếp bằng cách sử dụng Đa luồng trong C ++

Chúng tôi được cung cấp một mảng số nguyên không được sắp xếp. Nhiệm vụ là sắp xếp mảng bằng cách sử dụng kỹ thuật sắp xếp hợp nhất được thực hiện thông qua Đa luồng

Hợp nhất Sắp xếp

Sắp xếp hợp nhất là một kỹ thuật sắp xếp dựa trên kỹ thuật chia và chia, trong đó chúng ta chia mảng thành các nửa bằng nhau và sau đó kết hợp chúng theo cách được sắp xếp.

Thuật toán để triển khai sắp xếp hợp nhất là

kiểm tra xem có một phần tử trong danh sách rồi trả về phần tử đó không.
Mặt khác, Chia dữ liệu đệ quy thành hai nửa cho đến khi không thể chia thêm nữa.
Cuối cùng, hợp nhất các danh sách nhỏ hơn thành danh sách mới theo thứ tự được sắp xếp.

Đa luồng

Trong hệ điều hành, Chủ đề là quá trình nhẹ chịu trách nhiệm thực hiện một phần của tác vụ. Các luồng chia sẻ tài nguyên chung để thực hiện tác vụ đồng thời.

Đa luồng là một triển khai đa nhiệm trong đó chúng ta có thể chạy nhiều luồng trên một bộ xử lý để thực thi các tác vụ đồng thời. Nó chia nhỏ các hoạt động cụ thể trong một ứng dụng thành các luồng riêng lẻ. Mỗi luồng có thể chạy song song.

Ví dụ-:

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

Hết −Mảng được sắp xếp là:1, 2, 3, 4, 5, 7, 8, 9, 10

Giải thích −chúng tôi được cung cấp một mảng không được sắp xếp với các giá trị nguyên. Bây giờ chúng ta sẽ sắp xếp mảng bằng cách sử dụng sắp xếp hợp nhất với đa luồng.

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

Hết −Mảng được sắp xếp là:1, 3, 5, 21, 32, 45, 50

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Chúng ta sẽ bắt đầu bằng cách tạo các số ngẫu nhiên bằng phương thức rand () trong C ++ STL.
Tạo một mảng kiểu pthread_t, tức là P_TH [thread_size].
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước của một luồng. Bên trong vòng lặp, gọi phương thức pthread_create (&P_TH [i], NULL, Sorting_Threading, (void *) NULL) để tạo chuỗi với các giá trị mảng đã cho.
Gọi hàm dưới dạng comback_array (0, (size / 2 - 1) / 2, size / 2 - 1), merge_array (size / 2, size / 2 + (size-1-size / 2) / 2, size - 1) và merge_array (0, (size - 1) / 2, size - 1)
In mảng đã sắp xếp được lưu trữ trong arr [] kiểu số nguyên.
Bên trong hàm void * Sorting_Threading (void * arg)
- Khai báo một biến dưới dạng set_val thành temp_val ++, đầu tiên là set_val * (size / 4), kết thúc là (set_val + 1) * (size / 4) - 1 và mid_val thành first + (end - first) / 2
- Kiểm tra IF đầu tiên nhỏ hơn end, sau đó gọi Sorting_Threading (đầu tiên, mid_val), Sorting_Threading (mid_val + 1, end) và merge_array (đầu tiên, mid_val, end);
Bên trong hàm void Sorting_Threading (int first, int end)
- Khai báo biến là mid_val thành first + (end - first) / 2
- Kiểm tra IF đầu tiên dưới end, sau đó gọi Sorting_Threading (đầu tiên, mid_val), Sorting_Threading (mid_val + 1, end) và merge_array (first, mid_val, end)
Bên trong hàm void kết hợp_array (int first, int mid_val, int end)
- Khai báo các biến là int * bắt đầu thành mới int [mid_val - đầu tiên + 1], int * cuối cùng đến mới int [end - mid_val], temp_1 đến mid_val - đầu tiên + 1, temp_2 đến cuối - mid_val, i, j, k đến đầu tiên .
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn temp_1. Trong vòng lặp, đặt start [i] thành arr [i + first].
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn temp_2. Trong vòng lặp, đặt [i] cuối cùng thành arr [i + mid_val + 1]
- Đặt i là j thành 0. Vòng lặp bắt đầu Trong khi tôi nhỏ hơn temp_1 VÀ j nhỏ hơn temp_2. Bên trong while, hãy kiểm tra IF start [i] nhỏ hơn last [j] rồi đặt arr [k ++] bắt đầu [i ++]. ELSE, set arr [k ++] =last [j ++]
- Bắt đầu WHILE i nhỏ hơn temp_1 rồi đặt arr [k ++] =start [i ++]. Bắt đầu WHILE j ít hơn temp_2 rồi đặt arr [k ++] thành cuối cùng [j ++]

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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