Das Einfügungssortieren mit dynamischen Arrays bemeistern

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.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/AdvancedConceptsGroup(["Advanced Concepts"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp/BasicsGroup -.-> cpp/operators("Operators") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/ControlFlowGroup -.-> cpp/for_loop("For Loop") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/AdvancedConceptsGroup -.-> cpp/pointers("Pointers") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/user_input("User Input") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") subgraph Lab Skills cpp/operators -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/arrays -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/for_loop -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/while_loop -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/pointers -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/output -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/user_input -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} cpp/files -.-> lab-96119{{"Einfügungssortieren mit dynamischen Arrays"}} end

Ein dynamisches Array erstellen

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

Anzeige 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 Insertionsort-Algorithmus

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

Anzeige 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;

Freigabe des Arbeitsspeichers

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

    // Freigabe des Arbeitsspeichers
    delete [] arr;

    return 0;
}

Kompilieren und Ausführen des Programms

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.