Auswahlsortierung von dynamischen Arrays in C++

Einführung

In diesem Lab lernst du, wie du die Auswahlsortierung anwendest, um eine unsortierte dynamische Array in C++ mit dem Auswahlsortieralgorithmus zu sortieren.

Erstelle eine neue C++-Datei

Erstelle zunächst eine neue C++-Datei namens main.cpp im Verzeichnis ~/project.

touch ~/project/main.cpp

Implementiere den Auswahlsortieralgorithmus

Der Auswahlsortieralgorithmus funktioniert, indem er das kleinste Element auswählt und es am Anfang des Arrays platziert, dann das nächstkleinste Element aus dem Rest des Arrays auswählt und es an Index 1 platziert und so weiter, bis das Array vollständig sortiert ist. Hier ist, wie man den Auswahlsortieralgorithmus in C++ implementiert:

#include <iostream>
using namespace std;

// Funktion, um die Position zweier Elemente zu tauschen
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// Funktion, um den Auswahlsortieralgorithmus auszuführen
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // Um in absteigender Reihenfolge zu sortieren, ändere > in < in dieser Zeile.
      // Wähle in jeder Schleife das kleinste Element.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // Stelle min an der richtigen Position ein
    swap(&array[min_idx], &array[step]);
  }
}

In diesem Codeblock definieren wir eine Funktion swap(), um die Position zweier Elemente im Array zu tauschen, und eine Funktion selectionSort(), um den Auswahlsortieralgorithmus auf dem Array auszuführen.

Gib das Array ein

In diesem Schritt wirst du das dynamische Array eingeben, das sortiert werden muss. Du kannst dies tun, indem du den Benutzer aufforderst, die Elemente des Arrays nacheinander einzugeben:

// driver code
int main() {
  int size;
  cout<<"Enter the size of the array: ";
  cin>>size; //Eingabe der Größe des Arrays
  int* data = new int[size]; //Dynamisch Array deklarieren

  // Die Elemente des Arrays nacheinander eingeben
  for(int i = 0; i < size; i++) {
    cout<<"Enter element "<<i+1<<" : ";
    cin>>data[i];
  }

Führe die Auswahlsortierung durch

Jetzt, da wir das unsortierte Array haben, können wir den Auswahlsortieralgorithmus darauf anwenden, indem wir die zuvor definierte Funktion selectionSort() verwenden. Hier ist, wie man es macht:

  // Führe die Auswahlsortierung durch
  selectionSort(data, size);

Gebe das sortierte Array aus

Schließlich werden wir das sortierte Array mithilfe einer Schleife in einer Funktion namens printArray() in der Konsole ausgeben. Hier ist, wie man es macht:

  // Gebe das sortierte Array aus
  cout << "\nSorted array: ";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // Gebe den von dem dynamischen Array verwendeten Speicher frei
  delete[] data;
  return 0;
}

Kompiliere und führe den Code aus

Um den Code zu kompilieren und auszuführen, öffnen Sie das Terminal und navigieren Sie zum Ordner, in dem Ihre main.cpp-Datei gespeichert ist. Führen Sie dann die folgenden Befehle aus:

g++ main.cpp -o main
./main

Das sortierte Array sollte in der Konsole angezeigt werden.

Zusammenfassung

In diesem Lab haben Sie gelernt, wie man den Auswahlsortieralgorithmus verwendet, um ein unsortiertes dynamisches Array in C++ zu sortieren. Dazu mussten Sie das Array eingeben, den Auswahlsortieralgorithmus implementieren, die Sortierung ausführen, das sortierte Array ausgeben und dann den Code im Terminal kompilieren und ausführen. Mit diesen Fähigkeiten können Sie Arrays beliebiger Größe mithilfe der Auswahlsortierung sortieren.