Implémentation du tri par fusion en C++ en utilisant le multithreading

Nous obtenons un tableau d'entiers non triés. La tâche consiste à trier le tableau à l'aide d'une technique de tri par fusion mise en œuvre via le multi-threading

Tri par fusion

Le tri par fusion est une technique de tri basée sur la technique de diviser pour régner où nous diviserons le tableau en deux moitiés égales, puis les diviserons en un manière triée Combiné.

L'algorithme qui implémente le tri par fusion est

• Vérifiez s'il y a un élément

• Sinon, divisez les données en deux de manière récursive jusqu'à ce qu'elles ne puissent plus être divisées.

• Enfin, fusionnez les petites listes dans une nouvelle liste dans l'ordre trié.

Multi-threading

Dans le système d'exploitation, les threads sont des processus légers chargés d'effectuer certaines tâches. Les threads partagent des ressources communes pour effectuer des tâches simultanément.

Multi-threading est une implémentation du multitâche où nous pouvons exécuter plusieurs threads sur un seul processeur pour exécuter des tâches simultanément. Il décompose les opérations spécifiques au sein d’une seule application en threads distincts. Chaque thread peut s'exécuter en parallèle.

Par exemple :

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

Output−Le tableau trié est : 1, 2, 3, 4, 5, 7, 8, 9, 10

Explication- Nous obtenons un tableau non trié avec des valeurs entières. Nous allons maintenant trier le tableau en utilisant le tri par fusion multithread.

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

Output−Le tableau trié est : 1, 3, 5, 21, 32, 45, 50

Explication− On nous donne un tableau non trié avec des valeurs entières. Nous allons maintenant trier le tableau en utilisant le tri par fusion multithread.

Les méthodes utilisées dans le programme ci-dessous sont les suivantes -

• Nous allons commencer à générer des nombres aléatoires en utilisant la méthode rand() en C++ STL.

• Créez un tableau de type pthread_t, c'est-à-dire P_TH[thread_size].

Démarrez une boucle FOR de i à 0 jusqu'à ce que i soit inférieur à la taille du fil. À l'intérieur de la boucle, la méthode pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) est appelée pour créer un thread avec la valeur de tableau donnée.

• Appelez la fonction comme combine_array(0, (size/2 - 1)/2, size/2 - 1), combine_array(size/2, size/2 + (size-1-size/2)/ 2 . Size - 1) et merge_array(0, (size - 1)/2, size - 1)

• imprime le tableau trié stocké dans le type entier arr[].

À l'intérieur de la fonction void* Sorting_Threading(void* arg)

• Déclarez une variable de set_val à temp_val++, d'abord set_val * (size / 4), la fin est (set_val + 1) * (size / 4) - 1. mid_val est first + (end - first) / 2

• Vérifiez SI first est inférieur à end puis appelez Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) et combine_array(first, mid_val, end) ;

• À l'intérieur de la fonction void Sorting_Threading(int first, int end)

  • Déclarez la variable comme mid_val à first + (end - first) / 2

  • Vérifiez si IF est inférieur à end first, puis appelez Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) et merge_array(first, mid_val, end)

• function internal void merge_array(int first, int mid_val, int end)

  • déclarez la variable comme int * start to new int[mid_val - first + 1], int* last to new int[end - mid_val], temp_1 à mid_val - first + 1, temp_2 to end - mid_val, i, j, k to d'abord.

    li>

  • Démarrez une boucle FOR de i à 0 jusqu'à ce que i soit inférieur à temp_1. À l'intérieur de la boucle, définissez start[i] sur arr[i + first].

  • Démarrez une boucle FOR de i à 0 jusqu'à ce que i soit inférieur à temp_2. À l'intérieur de la boucle, définissez last[i] sur arr[i + mid_val + 1]

  • set i sur j sur 0. Commencez la boucle lorsque i est inférieur à temp_1 et j est inférieur à temp_2. En attendant, vérifiez si SI start[i] est inférieur à last[j], puis définissez arr[k++] sur start[i++]. Sinon, définissez arr[k++] = last[j++]

  • Démarrez quand i est inférieur à temp_1, puis définissez arr[k++] = start[i++]. Commencez lorsque j est inférieur à temp_2, puis définissez arr[k++] sur last[j++]

Exemple

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

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!