Implementieren Sie den Einfügungssortieralgorithmus in C++

In diesem Artikel wird veranschaulicht, wie Sie einen Einfügungssortieralgorithmus in C++ implementieren.

Implementieren Sie die Einfügungssortierung für den Container std::vector in C++

In dieser Anleitung zeigen wir Ihnen, wie Sie die Einfügungssortierung als separate Funktion implementieren, die eine Referenz auf das Objekt std::vector nimmt und den vorhandenen Inhalt modifiziert. Die Einfügungssortierung durchläuft jedes Element im Vektor. Es stellt sicher, dass alle Elemente vor der aktuellen Position sortiert werden, indem das aktuelle Element mit den vorherigen in Rückwärtsreihenfolge verglichen wird.

Im Allgemeinen spielt die Vergleichsreihenfolge keine große Rolle für die Leistung des Algorithmus, aber wir gehen von der Rückwärtsreihenfolge aus und implementieren den Code entsprechend. Wir gehen auch davon aus, dass die Elemente in aufsteigender Reihenfolge sortiert werden. In tatsächlichen Fällen sollte der generische Sortieralgorithmus jedoch in der Lage sein, eine benutzerdefinierte Vergleichsfunktion als Argument zu verwenden. Beachten Sie, dass die Vergleichsoperation oft eine Verschiebung des Elements nach rechts erzwingt, wenn das aktuelle Element kleiner als das vorherige ist. Letztere Operation wird mit einer weiteren verschachtelten for-Schleife implementiert, die die Funktion std::swap für Elemente aufruft, die in der falschen Reihenfolge sind.

Der folgende Codeausschnitt enthält die Funktion insertionSort, wobei die äußere for-Schleife für den gesamten Array-Durchlauf verantwortlich ist. Wir initialisieren den Iterator mit dem zweiten Element im Vektor, da die nächsten Schritte den Vergleich mit den vorherigen beinhalten – die innere Schleife iteriert vom aktuellen Element zum ersten, um sie zu vergleichen. Ergibt die Vergleichsfunktion true, wird das Paar getauscht. Beachten Sie, dass der Ausdruck else erzwingt, dass die innere Schleife unterbrochen wird, wenn sich herausstellt, dass mindestens ein vorheriges Element kleiner ist als das aktuelle Element.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort(vector<T> &vec) {
  for (auto it = vec.begin() + 1; it != vec.end(); ++it) {
    auto key = it;

    for (auto i = it - 1; i >= vec.begin(); --i) {
      if (*i > *key) {
        std::swap(*i, *key);
        key--;
      } else {
        break;
      }
    }
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  insertionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Alternativ können wir die Funktion insertionSort mit while-Schleifenkonstrukten neu implementieren, wenn letztere als lesbarere Form für den Benutzer bevorzugt werden. Zwei Algorithmen folgen einer ähnlichen Implementierungslogik, und beide verwenden die Funktion std::swap, um Elemente zu verschieben. Die Einfügungssortierung ist bei großen Datensätzen ein ziemlich ineffizienter Algorithmus und seine durchschnittliche Leistung beträgt O(n²).

Die Einfügungssortierung ähnelt einem anderen quadratischen Algorithmus, der als Auswahlsortierung bezeichnet wird. beide durchlaufen den Vektor. Nach den n Iterationen werden die ersten n Elemente sortiert. Allerdings wertet die Selektionssortierung im Gegensatz zur Einfügesortierung Vorwärtselemente ab der aktuellen Position aus.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort2(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  insertionSort2(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

43; 5; 123; 94; 359; -23; 2; -1; 
-23; -1; 2; 5; 43; 94; 123; 359; 

Die Einfügungssortierung kann in der Praxis im Vergleich zu anderen O(n²)-Algorithmen effizienter sein, da sie nicht immer das aktuelle Element mit jedem vorhergehenden vergleichen muss. Währenddessen muss die Auswahlsortierung immer jedes Element im unsortierten Unterarray durchsuchen, um das kleinste (oder das größte) Element zu finden. Beachten Sie, dass wir sowohl die Implementierung der Funktion insertionSort für den Vektor von std::string verwenden können, da die letztere Klasse die Überladungen des Vergleichsoperators implementiert. Das nächste Beispiel demonstriert seine grundlegende Verwendung mit dem String-Vektor und gibt die sortierte Wortliste aus.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void insertionSort(vector<T> &vec) {
  auto iter = vec.begin() + 1;
  while (iter != vec.end()) {
    auto key = iter;
    auto it = iter - 1;

    while (it >= vec.begin() && *it > *key) {
      std::swap(*it, *key);
      key--;
      it--;
    }
    iter++;
  }
}

int main() {
  vector<string> vec2 = {"highway", "song",  "work",
                         "borland", "death", "woman"};

  printVector(vec2);
  insertionSort(vec2);
  printVector(vec2);

  return EXIT_SUCCESS;
}

Ausgabe:

highway; song; work; borland; death; woman;
borland; death; highway; song; woman; work;