Einfügungssortieren mit dynamischen Arrays

Einführung

In diesem Lab werden wir lernen, wie man den Insertionsort-Algorithmus mit dynamischen Arrays in C++ implementiert. Dieser Algorithmus ist ein einfacher Sortieralgorithmus, der funktioniert, indem die Liste in zwei Teile, sortiert und unsortiert, unterteilt wird, und dann jedes Element der unsortierten Liste an die richtige Stelle in die sortierte Liste eingefügt wird.

Erstellen eines dynamischen Arrays

Zunächst müssen wir ein dynamisches Array von ganzen Zahlen mit einer Größe erstellen, die vom Benutzer bestimmt wird, und es mit zufälligen ganzen Zahlen zwischen 1 und 100 füllen.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Geben Sie die Größe des Arrays ein: ";
    cin >> size;

    // dynamisches Array erstellen
    arr = new int[size];

    // Array mit zufälligen ganzen Zahlen zwischen 1 und 100 füllen
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

Anzeigen des unsortierten Arrays

Als nächstes werden wir den Inhalt des unsortierten Arrays an den Benutzer ausgeben.

    // Anzeige des unsortierten Arrays
    cout << "Unsorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Implementierung des Einfügungssortieralgorithmus

Jetzt werden wir den Insertionsort-Algorithmus implementieren, der das Array in aufsteigender Reihenfolge sortieren wird.

    // Insertionsort
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

Anzeigen des sortierten Arrays

Wir werden den Inhalt des sortierten Arrays an den Benutzer ausgeben.

    // Anzeige des sortierten Arrays
    cout << "Sorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Speicher freigeben

Schließlich werden wir den Arbeitsspeicher freigeben, den das dynamische Array verwendet hat.

    // Freigabe des Arbeitsspeichers
    delete [] arr;

    return 0;
}

Programm kompilieren und ausführen

Speichern Sie die Datei als "sort.cpp" im Verzeichnis ~/project.

Kompilieren und führen Sie das Programm im Terminal aus:

$ cd ~/project
$ g++ sort.cpp -o sort
$./sort

Zusammenfassung

In diesem Lab haben wir gelernt, wie man den Insertionsort-Algorithmus mit dynamischen Arrays in C++ implementiert. Wir haben ein dynamisches Array mit einer Größe erstellt, die vom Benutzer bestimmt wird, es mit zufälligen ganzen Zahlen gefüllt, den Insertionsort-Algorithmus implementiert und schließlich das sortierte Array an den Benutzer ausgegeben. Wir haben auch gelernt, wie man den Arbeitsspeicher freigibt, den das dynamische Array verwendet hat.