Implementieren des Auswahlsortieralgorithmus in C++

In diesem Artikel wird erläutert, wie Sie den Auswahlsortierungsalgorithmus in C++ implementieren.

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

Unter den einfachen Sortieralgorithmen können Sie die Auswahlsortierung als einen der am einfachsten zu implementierenden betrachten; obwohl es die Komplexität O(n²) hat, und es macht es bei großen Vektoren völlig ineffizient.

Die Selektionssortierung kann als folgende Routine angegeben werden: Zuerst suchen wir den Minimalwert im Vektor und tauschen ihn mit dem ersten Element aus. Dann bewegen wir den Zeiger auf das zweite Element und suchen den minimalen Wert aus dem verbleibenden Untervektor, um mit dem zweiten Element zu tauschen. Wir fahren mit den vorherigen Schritten für den Rest des Vektors fort, während wir den Zeiger um ein Element nach dem anderen vorrücken.

Eine alternative Erklärung für die Auswahlsortierung könnte lauten, den Eingabevektor in zwei Teile zu unterteilenL: Der erste ist ein sortierter Untervektor und der zweite ist der verbleibende Untervektor der unsortierten Elemente (der in der ursprünglichen Reihenfolge ist). Da nicht davon ausgegangen werden kann, dass der sortierte Untervektor im gegebenen Vektor vorhanden ist, sollten wir das erste Element als Teiler zwischen den sortierten und unsortierten Untervektoren wählen. Wenn wir also beginnen, die Mindestwerte mit den Elementen an den Startpositionen zu tauschen. Der Vektor wird natürlich in sortierte und unsortierte Teile unterteilt.

Im folgenden Beispiel implementieren wir die Funktion selectionSort, die die Referenz auf das Objekt std::vector nimmt und eine direkte Änderung von Elementen durchführt. Wir haben den Algorithmus std::min_element verwendet, um den Mindestwert bei jeder Iteration zu finden; Dies hilft, den Algorithmus erstmals besser zu verstehen.

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

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

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

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::swap(*it, *std::min_element(it, vec.end()));
  }
}

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

  printVector(vec1);
  selectionSort(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 selectionSort mit der zweiten for-Schleife umschreiben, die den minimalen Wert für den verbleibenden unsortierten Untervektor jeder Iteration findet. Diese Version ist für die Algorithmus-Komplexitätsanalyse geeignet. Obwohl der Auswahlsortieralgorithmus eine quadratische Laufzeit hat, kann er bei kleineren Vektoren im Vergleich zu den O(nlogn)-Algorithmen wie Mergesort oder Heapsort überraschend effizient sein. Beachten Sie, dass wir immer noch eine STL-Funktion verwenden, std::swap, die in diesem Fall eine Operation mit konstanter Zeit ist und für ein kurzes Codebeispiel nützlich ist.

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

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

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

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

    for (auto i = it + 1; i != vec.end(); ++i) {
      if (*i < *min) min = i;
    }

    std::swap(*it, *min);
  }
}

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

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

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