Heap-Sort mit dynamischen Arrays

Einführung

In diesem Lab werden Sie lernen, wie Sie den Heap-Sort-Algorithmus mit dynamischen Arrays in C++ implementieren. Heap Sort ist ein auf Vergleichen basierender Sortieralgorithmus, der funktioniert, indem er die Eingabe in eine sortierte und eine unsortierte Region aufteilt und die unsortierte Region iterativ verkleinert, indem er das größte oder kleinste Element extrahiert und in die sortierte Region verschiebt.

Das dynamische Array erstellen

Wir werden eine neue Datei namens main.cpp im Verzeichnis ~/project mit dem folgenden Befehl erstellen:

touch ~/project/main.cpp

Zunächst werden wir ein dynamisches Array erstellen, um Elemente zu speichern. Wir werden den new-Operator verwenden, um während der Laufzeit des Programms Speicher dynamisch zuzuweisen.

int* arr;
arr = new int[size];

Heapify-Funktion

Als nächstes werden wir die heapify()-Funktion erstellen, um die Elemente im Array neu zu ordnen. Der Zweck der heapify()-Funktion besteht darin, die Heap-Eigenschaft aufrechtzuerhalten, was bedeutet, dass jeder Knoten größer oder gleich seinen Kindern ist.

void heapify(int* arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest!= i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

Heap-Sort-Funktion

Nach der Implementierung der heapify()-Funktion werden wir die heapSort()-Funktion erstellen, um das Array in aufsteigender Reihenfolge zu sortieren.

void heapSort(int* arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Hauptfunktion

Als letztes werden wir die main()-Funktion erstellen, um die Elemente vom Benutzer zu lesen und das sortierte Array mit dem Heap-Sort-Algorithmus anzuzeigen.

int main() {
    int size;
    cout << "Enter the number of elements: ";
    cin >> size;

    int* arr;
    arr = new int[size];

    cout << "Enter the elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    heapSort(arr, size);

    cout << "Sorted Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

Zusammenfassung

In diesem Lab haben Sie gelernt, wie man den Heap-Sort-Algorithmus mit dynamischen Arrays in C++ implementiert. Sie haben auch gelernt, wie man ein dynamisches Array erstellt, das Array zu einem Heap formt und das Array sortiert, um das sortierte Array in aufsteigender Reihenfolge anzuzeigen. Folgen Sie den Anweisungen, um den Beispielcode auszuführen und die Implementierung des Heap-Sort-Algorithmus zu üben.