Wie implementiert man Heap-Sortierung in C?

Blog

Wie implementiert man Heap-Sortierung in C?

Wie implementiert man Heap-Sortierung in C?

Computer sind wirklich gut darin, Dinge zu sortieren. Komplexe Sortieraufgaben erledigen sie im Handumdrehen. Wir müssen ihnen nur noch die Methode mitteilen, die für die jeweilige Sortieraufgabe verwendet werden soll. In diesem Artikel erfahren Sie, wie Sie Heap-Sort in Ihren Computersystemen verwenden C um Ihre Daten zu sortieren.

React-native-Kamera-Kit

Dieser Artikel konzentriert sich auf die folgenden Hinweise,

  • Grundlagen des binären Heaps
  • Den Algorithmus anhand eines Beispiels verstehen
  • Schreiben Sie ein Programm für Heap-Sort in C
  • Zeitkomplexität

Lassen Sie uns also mit dieser Heap-Sortierung in C-Artikel beginnen,

Gegenwärtig gibt es Hunderte von bekannten Sortieralgorithmen, und wenn Sie damit nicht zufrieden sind, können Sie Ihren eigenen Algorithmus mit ausreichendem Wissen über Datenstrukturen, Algorithmen und Sortierung erstellen. In diesem Beitrag lernen wir die Heap-Sortierung kennen, die eine weit verbreitete und auf binäre Heap-Datenstruktur basierende ist.

Grundlagen des binären Heaps

Abgesehen von der Sortieranwendung hat Binary Heap auch andere Anwendungen wie Priority Queue, Graph Algorithms, etc. Binary Heap ist eine baumartige Struktur bestehend aus Elternknoten und Kindknoten. Basierend auf der Beziehung zwischen dem Elternknoten und dem Kindknoten kann er weiter klassifiziert werden als

  1. Min. Haufen
  2. Max. Haufen

Heap-Sortierung in C: Min Heap

Min Heap ist ein Baum, in dem der Wert der Elternknotendie untergeordneten Knoten. Betrachten wir zum Beispiel ein Array- [5, 6, 11, 4, 14, 12, 2]. Das obige Bild ist die minimale Heap-Darstellung des angegebenen Arrays.

Beispiel - Heap-Sortierung in C++ - Edurekaac

Heap-Sortierung in C: Max. Haufen

Max Heap ist das Gegenteil von Min Heap in Bezug auf die Beziehung zwischen übergeordneten Knoten und untergeordneten Knoten. Hier der Wert der untergeordneten Knoten des übergeordneten Knotens. Betrachten wir dasselbe Array [5, 6, 11, 4, 14, 12, 2]

Beispiel für eine Heap-Sortierung in C++ - Edurekaac

Das obige Bild ist die Max-Heap-Darstellung des angegebenen Arrays. Jetzt wissen wir grundsätzlich, was Binäre Heaps sind und welche Typen sie haben. Diese Konzepte werden uns beim Verständnis des Heap-Sort-Algorithmus sehr helfen.

Lassen Sie uns mit diesem Artikel über Heap-Sortierung in C fortfahren,

Den Algorithmus anhand eines Beispiels verstehen

Bevor wir das Programm schreiben, werden wir den Ansatz verstehen, den wir verwenden werden, um das gegebene Array zu sortieren. Zuerst besprechen wir den Algorithmus, danach werden wir ihn mit einem Beispiel verstehen. Wir werden max Heap für unseren Anwendungsfall verwenden.

Hokkaido-Inu-Münzen-Preisvorhersage
  1. Zunächst werden wir den Benutzer bitten, einzugeben, dass sortiert werden soll.
  2. Sobald das Array empfangen wurde, müssen wir einen Haufen der vom Array empfangenen Zahlen erstellen, um sie in aufsteigender Reihenfolge zu sortieren.
  3. Jetzt müssen wir einen maximalen Heap aus diesem Heap erstellen. Es gibt eine Regel, die befolgt werden muss, um einen maximalen Heap zu erstellen, d. h. der Wert des übergeordneten Knotens sollte der Wert seiner untergeordneten Knoten sein.
  4. Nachdem der Baum erstellt wurde, müssen wir die obige Bedingung überprüfen. Wenn der Wert des untergeordneten Knotens größer ist als der des übergeordneten Knotens, müssen wir ihre Werte austauschen und erneut prüfen, bis die in Schritt 3 erwähnte Bedingung angegeben ist.
  5. Sobald die Bedingung erfüllt ist und alle Elemente entsprechend angeordnet sind. Wir müssen den Wurzelknoten mit dem letzten Knoten austauschen.
  6. Entfernen Sie nach dem Auslagern den letzten Knoten aus dem Heap. Wir entfernen es, wie es sortiert wurde.
  7. Wiederholen Sie die Schritte 4, 5 und 6, bis ein Element im Heap übrig ist.

Wenn Sie den obigen Algorithmus anhand eines Beispiels verstehen, erhalten Sie ein tieferes Verständnis des gesamten Prozesses. Wir werden das gleiche Array verwenden, das wir oben verwendet haben, um die Dinge besser zuordenbar zu machen.

Beispiel Array = [5, 6, 11, 4, 14, 12, 2]

Unity ml-Agenten-Tutorial

Beispiel für eine Heap-Sortierung in C++ - Edurekaac

Ja, das Beispiel, das wir betrachtet haben, ist ein großes, aber lassen Sie uns verstehen, was passiert, wenn es darum geht, Heap-Sort in C oder in einer anderen Sprache zu implementieren.

  1. Im ersten Schritt haben wir damit begonnen, einen Heap zu erstellen, da 11 größer als 5 ist, haben wir sie getauscht, um einen maximalen Heap zu erstellen
  2. Dann haben wir andere Mitglieder des Arrays eingeführt und 6 mit 14 ausgetauscht, um einen maximalen Heap zu erstellen
  3. In Schritt 4 und 5 haben wir 15 mit 11 bzw. 12 mit 5 vertauscht.
  4. In Schritt 5 wird unser maximaler Heap erstellt.
  5. Wir haben in Schritt 6 14 durch 2 getauscht, da wir in unserem vorherigen Abschnitt besprochen hatten, dass wir, sobald der maximale Heap erstellt ist, den ersten Knoten mit dem letzten Knoten austauschen und den letzten Knoten entfernen müssen, daher haben wir 14 entfernt
  6. Um den maximalen Heap wieder zu erstellen, haben wir 5 mit 2 getauscht
  7. Nach der Erstellung von Max Heap haben wir 2 durch 12 getauscht und 12 . entfernt
  8. Um wieder einen maximalen Heap zu erstellen, haben wir 11 mit 2 und 6 mit 2 getauscht, danach haben wir 11 und 2 getauscht, da der maximale Heap erstellt und entfernt wurde 11
  9. In Schritt 12 und 13 tauschen wir 6 mit 2 bzw. 4 mit 2 aus
  10. Da wir einen maximalen Heap haben, tauschen wir 6 mit 2 aus und entfernen 6

An dieser Stelle werden Sie feststellen, dass die Zahlen in aufsteigender Reihenfolge entfernt und von rechts nach links im Array platziert werden

  1. In Schritt 15 tauschen wir 5 mit 2 aus, um einen maximalen Heap zu erstellen, und tauschen erneut 2 mit 5 aus und entfernen 5
  2. Sobald wir 2 mit 4 austauschen, um den maximalen Heap zu erstellen, und erneut 4 mit 2 austauschen, um 4 zu entfernen, sind wir fast fertig.
  3. Schließlich haben wir noch 1 Element in unserem Heap, d.h. 2.
  4. Dieses Element wird an der 0. Position des Arrays platziert und der Algorithmus ist abgeschlossen.

Kommen wir nun zum Programmierteil,

Schreiben Sie ein Programm für die Heap-Sortierung in C

Jetzt haben wir ein gutes Verständnis des Sortieralgorithmus, den wir verwenden werden. Also lasst uns anfangen

#include #include void Adjust(int Heap_of_Numbers[],int i) /*Function to arrange the elements in the heap*/ { int j; int copy; int Number; int Reference = 1; Number=Heap_of_Numbers[0]; while(2*i<=Number && Reference==1) { j=2*i; if(j+1 Heap_of_Numbers[j]) j=j+1; if( Heap_of_Numbers[j] =1;i--) Adjust(heap,i); } int main() { int heap[30]; int NumberofElements; int i; int LastElement; int CopyVariable; printf('Enter the number of elements present in the unsorted Array:'); scanf('%d',&NumberofElements); printf('nEnter the members of the array one by one:'); /* Asking for the elements of the unsorted array*/ for(i=1;i 1) /*Loop for the Sorting process*/ { LastElement=heap[0]; CopyVariable=heap[1]; heap[1]=heap[LastElement]; heap[LastElement]=CopyVariable; heap[0]--; Adjust(heap,1); } printf('nSorted Array:n');/*Printing the sorted Array*/ for(i=1;i<=NumberofElements;i++) printf('%d ',heap[i]); return 0; }

Ich habe das gleiche Array verwendet, um unsere Ergebnisse zu überprüfen, und wie Sie im Ausgabefenster sehen können, haben wir das gleiche Ergebnis erhalten. Die manuelle Durchführung erforderte viele Schritte und es besteht die Möglichkeit von Fehlern. Daher kann uns dieses Programm helfen, diese Probleme zu lösen und unsere Zeit zu sparen. Ausgabe

Dies bringt uns zum letzten Teil dieser Heap-Sortierung in C-Artikel,

Heap-Sortierung in C: Zeitkomplexität

Nachdem wir nun alle Schlüsselkonzepte verstanden haben, müssen wir den wichtigsten Aspekt eines jeden Algorithmus überprüfen, nämlich seine Zeitkomplexität. Für diejenigen, die diesen Begriff nicht kennen, hier eine kurze Erklärung. Die Zeitkomplexität ist ein Maß für die Zeit, die ein Algorithmus benötigt, um die Ausgabe zu berechnen.

beste Template-Engine für Express

Die Zeitkomplexität von Heap Sort ist O(nLogn).

Damit sind wir am Ende dieses Artikels zum Thema „Heap-Sortierung in C“ angelangt. Ich hoffe, Sie fanden dies informativ und hilfreich.

#c #c-programmierung