Implementieren der Zusammenführungssortierung in C++ mithilfe von Multithreading

Wir erhalten ein unsortiertes Array von ganzen Zahlen. Die Aufgabe besteht darin, das Array mithilfe der durch Multithreading implementierten Merge-Sort-Technik zu sortieren sortierte Art und Weise kombiniert.

Der Algorithmus, der die Zusammenführungssortierung implementiert, ist

Überprüfen Sie, ob ein Element vorhanden ist

• Ansonsten teilen Sie die Daten rekursiv in zwei Hälften auf, bis sie nicht mehr geteilt werden können.

• Zum Schluss fügen Sie die kleineren Listen in sortierter Reihenfolge zu einer neuen Liste zusammen.

• Multi-Threading

Im Betriebssystem sind

Multi-Threading ist eine Implementierung von Multitasking, bei der wir mehrere Threads auf einem einzelnen Prozessor ausführen können, um Aufgaben gleichzeitig auszuführen. Es unterteilt bestimmte Vorgänge innerhalb einer einzelnen Anwendung in separate Threads. Jeder Thread kann parallel laufen.

Zum Beispiel:

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

Output−Das sortierte Array ist: 1, 2, 3, 4, 5, 7, 8, 9, 10

Erklärung- Wir erhalten ein unsortiertes Array mit ganzzahligen Werten. Jetzt sortieren wir das Array mithilfe der Multithread-Zusammenführungssortierung.

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

Output−Das sortierte Array ist: 1, 3, 5, 21, 32, 45, 50 p>

Erklärung−Wir erhalten ein unsortiertes Array mit ganzzahligen Werten. Jetzt sortieren wir das Array mithilfe der Multithread-Zusammenführungssortierung.

Die im folgenden Programm verwendeten Methoden sind wie folgt:

Wir beginnen mit der Generierung von Zufallszahlen mithilfe der Methode rand() in C++ STL.

• Erstellen Sie ein Array vom Typ pthread_t, also P_TH[thread_size].

• Starten Sie eine FOR-Schleife von i bis 0, bis i kleiner als die Größe des Threads ist. Innerhalb der Schleife wird die Methode pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) aufgerufen, um einen Thread mit dem angegebenen Array-Wert zu erstellen.

Rufen Sie die Funktion als combine_array(0, (size/2 - 1)/2, size/2 - 1), combin_array(size/2, size/2 + (size-1-size/2)/ 2 auf . Size - 1) und merge_array(0, (size - 1)/2, size - 1)

• drucken das sortierte Array, das im Ganzzahltyp arr[] gespeichert ist.

• Innerhalb der Funktion void* Sorting_Threading(void* arg)

Deklarieren Sie eine Variable von set_val bis temp_val++, zuerst set_val * (Größe / 4), Ende ist (set_val + 1) * (Größe / 4) - 1. mid_val ist first + (end - first) / 2

• Überprüfen Sie, ob first kleiner als end ist, und rufen Sie dann Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end) und kombinieren_array(first, mid_val, end) auf. ;

Inside function void Sorting_Threading(int first, int end)

• Deklarieren Sie die Variable als mid_val to first + (end - first) / 2

  • Überprüfen Sie, ob IF kleiner als end first ist. Rufen Sie dann Sorting_Threading(first , mid_val), Sorting_Threading(mid_val + 1, end) und merge_array(first, mid_val, end) auf Deklarieren Sie die Variable als int * start to new int[mid_val - first + 1], int* last to new int[end - mid_val], temp_1 to mid_val - first + 1, temp_2 to end - mid_val, i, j, k to Erste.

  • Starten Sie eine FOR-Schleife von i nach 0, bis i kleiner als temp_1 ist. Setzen Sie innerhalb der Schleife start[i] auf arr[i + first].
• Starten Sie eine FOR-Schleife von i nach 0, bis i kleiner als temp_2 ist. Setzen Sie innerhalb der Schleife last[i] auf arr[i + mid_val + 1]
  • setze i to j auf 0. Beginnen Sie mit der Schleife, wenn i kleiner als temp_1 und j kleiner als temp_2 ist. Überprüfen Sie in der Zwischenzeit, ob IF start[i] kleiner als last[j] ist, und setzen Sie dann arr[k++] auf start[i++]. Andernfalls setze arr[k++] = last[j++]
    li>Start, wenn i kleiner als temp_1 ist, und setze dann arr[k++] = start[i++]. Beginnen Sie, wenn j kleiner als temp_2 ist, und setzen Sie dann arr[k++] auf last[j++]

Das obige ist der detaillierte Inhalt vonImplementieren der Zusammenführungssortierung in C++ mithilfe von Multithreading. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!