Rekursions- und Sortieralgorithmen

Ich werde so ziemlich alle Sortieralgorithmen rekursiv präsentieren, daher sollten wir wahrscheinlich über Rekursion sprechen. Rekursion ist eine wirklich umwerfende Technik, sobald Sie den Dreh raus haben. Es ist auch die Grundlage für das, was die „mathematische Interpretation“ der Computerprogrammierung genannt werden könnte, also wenn Sie ein CSci Major sind, müssen Sie sich früher oder später damit vertraut machen. Schauen wir uns also einige einfache Algorithmen an, sowohl iterativ (mit Schleifen) als auch rekursiv.

Finden der Fakultät

Die Fakultät von n ist definiert als das Produkt \(n (n-1) (n-2) \ldots (2) (1)\), dh das Produkt aller ganzen Zahlen bis einschließlich n. Es ist einfach zu schreibenals Schleife:

int factorial_iter(int n) { int r = 1; // Factorial of 0 is 1 for(int i = 1; i <= n; ++i) r *= i; return r;}

Um diesen oder einen anderen Algorithmus rekursiv zu schreiben, müssen wir zwei Fragen stellen:

  • Was ist der kleinste Fall, der Fall, in dem ich die Antwort sofort geben kann? Dies wird als „Basisfall“ bezeichnet. (Manchmal kann es mehr als einen kleinsten Fall geben, und das ist in Ordnung.)

  • Für alles, was nicht der kleinste Fall ist, wie zerlege ich es, um es kleiner zu machen? Dies nennt man den rekursiven Fall.

Für die Fakultät ist der Basisfall, was passiert, wenn \ (n = 0\): Die Schleife wird überhaupt nicht ausgeführt und 1 wird zurückgegeben. So können wir unsere rekursive Version mit starten

int factorial_rec(int n) { if(n == 0) return 1; else ...}

Um den rekursiven Fall zu konstruieren, müssen wir uns ansehen, was passiert, wenn n > 0 . Insbesondere, wie können wir brechen \(n!\) nach unten in einige \(n‘ !, n‘ < n\)?Der häufigste Fall ist \(n‘ = n – 1\).

Eine Möglichkeit, dies zu betrachten, besteht darin, anzunehmen, dass wir bereits den Wert von \((n-1)!\), und wir wollen \(n!\) daraus. Das heißt, angenommen,factorial_rec(n - 1) wird funktionieren und uns die richtige Antwort geben; wir brauchen nurum die Fakultät von n daraus zu konstruieren. Wie können wir das machen?\(n! = n (n-1)!\). Also schreiben wir unseren rekursiven Fall so:

int fact(int n) { if(n == 0) return 1; else return n * fact(n - 1);}

Nehmen wir uns eine Minute Zeit, um durch den Prozess des Rechnens zu gehen factorial_rec(3):

  • fact(3) = 3 * fact(2)

  • fact(2) = 2 * fact(1)

  • fact(1) = 1 * fact(0)

  • fact(0) = 1 und an diesem Punkt können wir uns wieder nach oben arbeiten und das Ergebnis 3 * 2 * 1 * 1 = 6 .

Induktiver Beweis

Wie zeigen wir, dass eine Funktion das tut, was sie tun soll? Wir könnten es testen, es tausende oder Millionen Mal ausführen und überprüfen, ob seine Ausgabe dem entspricht, was wir erwarten, aber dies erfordert, dass wir einen unabhängigen Weg finden, um zu definieren, was die Funktion tut (z. eine andere Art der Berechnung der Fakultät), die selbst falsch sein kann, und darüber hinaus können wiederholte Tests uns immer nur ein statistisches Vertrauen geben, dass unser Algorithmus korrekt ist. Wenn wir sein wollensichern, dann brauchen wir einen logischen oder mathematischen Beweis, dass es richtig ist. Bei rekursiven Funktionen erfolgt dies häufig in Form eines Beweises durch Induktion. Ein induktiver Beweis ist eine Art mathematisches Äquivalent zu einer rekursiven Funktion.Wie eine rekursive Funktion hat sie Basisfall (e) (tatsächlich einen Basisfall für jeden Basisfall in der Funktion), und die Basisfälle sind normalerweise einfach. Es hat auch induktive Fälle (einen für jeden rekursiven Fall in der Funktion), die etwas schwieriger sind, aber es uns ermöglichen, so etwas wie Rekursion zu machen.

Betrachten Sie das obige Beispiel. Wir wollen beweisen, dass fact(n) =\(n!\), wobei die Definition von \(n! = n(n-1)(n-2)\ldots(2)(1), 0! = 1\).

Beweis durch Induktion für n (Für welche Variable wir auch immer die Rekursion durchführen, wir sagen, wir machen „Beweis durch Induktion“ für diese Variable):

  • Basisfall, \(n = 0\) Dann fact(0) = 1 =\(0!\) und wir sind fertig.

  • Induktiver Fall: Im induktiven Fall versuchen wir zu beweisen, dass fact(n) =\(n!\)` für einige \(n > 0\). Wir können die linke und rechte Seite aufschlüsseln und sehen, dass wir tatsächlich

    $$n \cdot \mathtt{fact}(n-1) = n ! = n (n-1) (n-2) \ldots (2)(1)$$

    Dividiert man durch \(n\), erhält man

    $$\mathtt{fact}(n-1) = (n-1)(n-2) \ldots (2)(1) = (n-1)!$$

    Mit anderen Worten, wir haben das Problem des Beweises reduziert, dass fact(n) =\(n!\) zum Problem des Beweises, dass fact(n-1) =\((n-1)!\). Das scheint nicht nützlich zu sein, aber wie in einer rekursiven Funktion, in der wir die Funktion selbst mit einem kleineren Argument aufrufen können, können wir in einem induktiven Beweis den Beweis selbst als Annahme für ein kleineres \(n\) . Wir nennen diese Annahme die induktive Hypothese und es sieht so aus:

    $$\ text{Annehmen}\qquad\mathtt{Tatsache}(n‘) = n‘! \qquad \text{für alle}\; n‘ < n$$

    Wenn wir \(n‘ = n-1\) dann haben wir

    $$\text{Annehmen}\qquad\mathtt{fact}(n-1) = (n-1)!$$

    Das ist genau das, was wir oben brauchten! Wenn wir das Obige ersetzen, erhalten wir

    $$(n-1)! = (n-1)!$$

    und wir sind fertig.

Wie die Rekursion ist das Herzstück eines induktiven Beweises die Anwendung des Beweises selbst als Annahme über „kleinere“ Werte (\(n‘ < n\)). Technisch gibt es zwei Arten von induktiven Beweisen:

  • “ Natürliche Zahleninduktion“ lässt uns nur die Annahme über \(n’= n-1\) machen. Das heißt, wir können nur von einer „Eingabe“ ausgehen, die kleiner als das Original ist.

  • “ Starke Induktion“ können wir jede \(n‘ < n\) . Sie können die starke Induktion überall dort verwenden, wo Sie die Induktion natürlicher Zahlen verwenden können, dies ist jedoch nicht immer erforderlich.

Die ganzzahlige Exponentenberechnung

Erinnerst du dich, als wir die Laufzeitkomplexität unserer „optimierten“ \(O(\log n)\) Funktion zum Finden von a \(b^n\) ? Wir können auch eine rekursive Version davon schreiben. Noch einmal, wir müssen fragen

  • Was ist der Basisfall? In diesem Fall ist es, wenn \(n = 0\). In diesem Fall ist \(b^0 = 1\) , egal was f ist (es gibt einige Debatten über \(0^ 0\)).

  • Was ist der rekursive Fall? Wie zerlegen wir \ (b ^ n\) in \(b ^ {n‘}\)? Hier nehmen wir unsere Warteschlange aus unserer früheren Implementierung:

    $$b^n = (b^{n/2})^2 \quad\text{if } n \text{ is even}$$
    $$ b^n = b \cdot b^{n-1} \quad\text{wenn } n \text{ ungerade ist}$$

Dies gibt uns die folgende Definition:

float powi(float b, int n) { if(n == 0) return 1; else if(n % 2 == 0) { // Even float fp = powi(b, n / 2); return fp * fp; } else if(n % 2 == 1) // Odd return f * powi(b, n - 1);}

Dies hat die gleiche Komplexität wie die schleifenbasierte Version und ist wohl einfacher.

Wenn wir in diesem Fall beweisen wollen, dass \(\mathtt{powi}(b,n) = b^n\) , benötigen wir eine starke Induktion, da einer der rekursiven Fälle die Eingabe um etwas anderes als nur -1 verkleinert.

Beweis, dass \(\mathtt{powi}(b,n) = b^n\) durch starke Induktion auf \(n\):

  • Basisfall: \(n = 0\)

    Wenn wir uns dann das Programm ansehen, erhalten wir \(\mathtt{powi}(n,0) = 1 = b^ 0\) und wir sind fertig.

  • Induktiver Fall: \(n > 0\), beweise \(\mathtt{powi}(b,n) = b ^ n\). Hier gibt es tatsächlich zwei induktive Fälle, jeweils einen für die beiden rekursiven Fälle in der Funktion. Unsere induktive Hypothese (Annahme) ist

    $$\mathtt{powi}(b,n‘) = b^{n‘}\qquad \text{für alle}\; n‘ < n$$
    • Fall 1, \(n\) ist gerade. Wenn wir dann den Aufruf von powi durch seinen Rückgabewert ersetzen, haben wir

      $$\mathtt{powi}(b, n / 2)^2 = b^n$$ $$\mathtt{powi}(b, n / 2)^2 = (b^{n/2})^2$$

      Die Quadratwurzel beider Seiten nehmen:

      $$\mathtt{powi}(b, n/2) = b^{n/2}$$

      an diesem Punkt können wir das IH mit \(n‘ = n/2\) anwenden und

      $$b^{n/2} = b^{n/2}$$
    • Fall 2, \(n\) ist ungerade. Wenn wir dann powi erweitern, erhalten wir

      $$b \cdot \mathtt{powi}(b,n-1) = b \cdot b^{n-1}$$ $$\mathtt{powi}(b,n-1) = b^{n-1} (\text{ dividieren durch} b)$$ $$b^{n-1} = b^{n-1}\qquad\text{von IH,} (n‘ = n-1)$$

    Und der Beweis ist vollständig

Gegenseitige Rekursion

Gegenseitige Rekursion ist, wenn wir mehrere rekursive Funktionen in Bezug aufeinander definieren. Betrachten Sie beispielsweise die folgende Definition von gerade und ungerade:

  • Eine natürliche Zahl n ist gerade, wenn \(n-1\) ungerade ist.

  • Eine natürliche Zahl n ist ungerade, wenn \(n-1\) gerade ist.

  • \(1\) ist ungerade, ist \(0\) gerade. (Dies sind unsere Basisfälle.)

Wir können dann zwei Funktionen (Prädikate) definieren, die sich rekursiv aufeinander beziehen:

bool is_even(int n) { if(n == 0) return true; else if(n == 1) return false; else return is_odd(n - 1);}bool is_odd(int n) { if(n == 0) return false; else if(n == 1) return true; else return is_even(n - 1);}

Wenn wir die Verarbeitung der Bestimmung von is_even(4) verfolgen, werden wir sehen, dasses springt zwischen is_even und is_odd hin und her.

Binäre Suche

Wir haben eine binäre Suche iterativ durchgeführt, können sie aber auch rekursiv durchführen:

  • Es gibt zwei Basisfälle: wenn wir den Artikel finden oder wenn der Suchraum auf 0 reduziert wird (was darauf hinweist, dass der Artikel nicht gefunden wurde).

  • Der rekursive Fall vergleicht den Wert des Ziels mit dem Wert am aktuellen Mittelpunkt und reduziert dann die Größe des Suchraums (indem entweder die linke oder die rechte Seite rekursiv durchsucht wird).

Das sieht so aus

template<typename T>int binary_search(const vector<T>& data, int low = 0, int high = data.size()-1, const T& target) { if(low > high) return -1; int mid = low + (high - low) / 2; // Why did I do this? if(data.at(mid) == target) return mid; else if(data.at(mid) < target) // Search right return binary_search(data, mid+1, high, target); else if(data.at(mid) > target) // Search left return binary_search(data, low, mid-1, target);}

Andere Beispiele: Zählen der Anzahl der Kopien in einem Vektor. Für jede Rekursion im Vektorstil müssen wir unseren „Startplatz“ innerhalb des Vektors verfolgen. Dies liegt daran, dass wir den Vektor selbst nicht verkleinern können, also müssen wir eine Markierung einfügen, die zeigt, wo wir anfangen. Wir können dies auf zwei Arten tun, mit einem int start Parameter oder mit Iteratoren.

template<typename T>int count(vector<T> data, int start, T target) { if(start == data.size()) return 0; else return (data.at(start) == target) + count(data, start + 1, target);}

Mit Iteratoren:

template<typename T, typename It>int count(It start, It finish, T target) { if(start == finish) return 0; else return (*start == target) + count(start + 1, finish, target);}

Iteratoren sind wie Zeiger.

Sortieralgorithmen

Ein Sortieralgorithmus ist eine Funktion, die eine Sequenz von Elementen verwendet und irgendwie eine Permutation von ihnen konstruiert, so dass sie auf irgendeine Weise geordnet sind.Normalerweise wollen wir, dass die Dinge nach den normalen Vergleichsoperatoren geordnet werden, so dass, wenn a < b dann kommt a vor b in der endgültigen Permutation.Immer noch, Es gibt ein paar Dinge, die wir sicherstellen müssen, dass wir es richtig machen:

  • Natürlich können wir keine Elemente durch den Prozess verlieren.

  • Das Original kann Duplikate enthalten, in diesem Fall sollte die Ausgabe die gleiche Anzahl von Duplikaten enthalten.

  • Der Einfachheit halber erlauben wir das Sortieren einer leeren Sequenz (die beim Sortieren zu einer weiteren leeren Sequenz führt)

Mit dem Sortieren sind einige Begriffe verbunden, die Sie unbedingt beachten sollten:

  • Stabilität – Wenn die Eingabesequenz Elemente enthält, die als gleich verglichen werden, aber unterschiedlich sind (z. B. Mitarbeiter mit identischen Namen, aber ansonsten unterschiedlichen Personen), stellt sich die Frage, ob sie in der Ausgabesequenz in derselben Reihenfolge wie im Original vorkommen. Z.B., wenn Mitarbeiter „John Smith“ # 123 vor „John Smith“ # 234 in der ursprünglichen Sequenz kam, dann sagen wir, dass eine Sortierung stabil ist, wenn # 123 vor # 234 im Ergebnis ist.

    Stabilität ist wichtig, wenn eine Sequenz nach mehreren Kriterien sortiert wird. Wenn wir beispielsweise nach dem Vornamen sortieren, dann nach dem Nachnamen, gibt uns eine instabile Sortierung nicht das gewünschte Ergebnis: Die Vornameneinträge werden alle durcheinander gebracht.

  • Anpassungsfähigkeit – einige Eingabesequenzen sind bereits teilweise (oder vollständig) sortiert; ein anpassbarer Sortieralgorithmus läuft bei teilweise sortierten Eingaben schneller (in Big-O-Begriffen). Die optimale Laufzeit für eine vollständig sortierte Eingabe ist \(O (n)\), die Zeit, die benötigt wird, um zu überprüfen, ob die Eingabe bereits sortiert ist.

  • In-Place – Ein In-Place-Sortieralgorithmus benötigt keinen zusätzlichen Speicherplatz (dh seine Speicherkomplexität beträgt \ (O (1) \)) zum Sortieren. Einige Algorithmen können nicht an Ort und Stelle verwendet werden und müssen eine separate Ausgabesequenz mit der gleichen Größe wie die Eingabe erstellen, um die Ergebnisse zu schreiben.

  • Online – Einige Datensätze sind zu groß, um überhaupt in den Speicher zu passen. Ein Online-Sortieralgorithmus erfordert, dass alle seine Daten zugänglich sind (im Speicher). Offline-Sortieralgorithmen können Daten sortieren, die sich teilweise im Speicher, teilweise auf der Festplatte oder einem anderen „langsamen“ Speicher befinden, ohne deren zeitliche Komplexität zu beeinträchtigen.

Auswahlsortierung

Wir haben uns bereits die Auswahlsortierung angesehen, also schauen wir es uns noch einmal an:

  • Um eine Liste von Elementen automatisch zu sortieren, suchen wir zuerst das kleinste Element in der gesamten Liste und setzen es an den Anfang.

  • Dann finden wir den kleinsten Gegenstand in allem nach dem ersten Gegenstand und setzen ihn an zweiter Stelle.

  • Fahren Sie fort, bis nichts mehr unsortiert ist.

Die Auswahlsortierung teilt die Liste effektiv in den sortierten Bereich am Anfang und den unsortierten Bereich am Ende auf. Die sortierte Region wächst, währendDie unsortierte Region schrumpft.

Auswahlsortierung ist nicht stabil.

Iterativ sieht das so aus:

template<typename T>void selection_sort(vector<T> data) { for(auto it = begin(data); it != end(data)-1; ++it) { // Find smallest auto smallest = it; for(auto jt = it+1; jt != end(data); ++jt) if(*jt < *smallest) smallest = jt; // Swap it into place swap(it, smallest); }}

Lassen Sie uns dies an einem kleinen Beispiel nachzeichnen, um ein Gefühl dafür zu bekommen, wie es funktioniert.

Wie können wir dies rekursiv implementieren? Anstatt das tatsächlichevector zu übergeben, werden wir nur die Iteratoren an den Anfang und das Ende des Vektors übergeben. Warum wir das tun, wird in Kürze offensichtlich:

template<typename Iterator>void selection_sort(Iterator first, Iterator last) { ...}

Lassen Sie uns die Rekursion analysieren:

  • Der Basisfall ist, wenn last == first + 1 . Das bedeutet, dass es nur 1 Element gibt und eine 1-Element-Liste immer sortiert ist.

  • Der rekursive Fall ist, wenn last - first > 1 . In diesem Fall brechen wir es rekursiv auf, indem wir

    • Das Minimum der Region finden und am Anfang platzieren.
    • Rekursiv Auswahl-Sortierung first+1 durch last (weil das Element bei first jetzt an der richtigen Stelle ist).
template<typename Iterator>void selection_sort(Iterator first, Iterator last) { if(last - first == 1) return; // 1 element, nothing to sort else { // Find minimum Iterator smallest = first; for(Iterator it = first; it != last; ++it) if(*it < *smallest) smallest = it; // Swap into place swap(*smallest, *first); // Recursively sort the remainder selection_sort(first + 1, last); }}

Zeichnen wir dafür den Rekursionsbaum. Wir werden die Schleife nicht durchlaufen, wir werdennur (vorerst) davon ausgehen, dass es richtig funktioniert.

DIAGRAMM

Analyse des Sortieralgorithmus

Neben der Analyse der allgemeinen Best- / Worst-Case-Big-O-Laufzeit eines Sortieralgorithmus werden häufig auch zwei weitere Laufzeitfunktionen analysiert:

  • Die Anzahl der Vergleiche zwischen Elementen. Dies zählt nur Vergleiche zwischen den zu sortierenden Objekten, nicht den Vergleich (z. B.) einer Schleifenzählvariablen.

  • Die Anzahl der Swaps zwischen Elementen.

Die Analyse der Anzahl der Vergleiche und Swaps ist nützlich, da diese Operationen im Mittelpunkt jedes Sortieralgorithmus stehen: Wir können nicht wissen, ob Elemente nicht in Ordnung sind, bis wir sie vergleichen (und wenn die Elemente komplex sind, kann der Vergleich eine nicht triviale Zeit in Anspruch nehmen) Zeit), und wir können sie nicht in die richtige Reihenfolge bringen, ohne sie zu verschieben – dh sie zu tauschen.

Bubble sort

Bubble sort ist ein Sortieralgorithmus, der nicht wirklich für die rekursive Implementierung geeignet ist. Die Idee ist, benachbarte Elemente in der Eingabe zu vergleichen (z., a und a) und tauschen Sie sie aus, wenn sie nicht in Ordnung sind. Wir beginnen am Anfang der Eingabe und gehen durch sie hindurch und tauschen unseren Wegbis zum Ende. Nach einem solchen Durchgang hat das größte Element bis zum letzten Element des Arrays „geblasen“. Dann können wir einen weiteren Pass machen, aber diesmal überspringen wir das letzte Element. Während die Auswahlsortierung von vorne immer kleinere Pässe machte, macht die Blasensortierung vom Ende aus immer kleinere Pässe.

Die Blasensortierung ist stabil.

Eine Implementierung sieht ungefähr so aus:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) swap(data.at(i), data.at(i + 1));}

Wie implementiert, ist diese Funktion sowohl im besten als auch im schlechtesten Fall von Ordnung \ (O (n ^ 2) \); verschachtelte Schleife, mit der gleichen „dreieckigen“ Struktur, die wir zuvor gesehen haben.Wir können tatsächlich eine einfache Optimierung implementieren: Wenn wir in der inneren Schleife keine Swaps durchführen, wird die Eingabe sortiert und wir können aufhören. Wenn wir dies überprüfen, können wir möglicherweise vorzeitig aussteigen.

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); sorted = false; } if(sorted) return; }}

Was sind die besten und schlimmsten Fälle?

  • Der beste Fall ist, wenn die Eingabe bereits sortiert ist. In diesem Fall machen wir einen Durchgang durch den Vektor (um zu überprüfen, ob er sortiert ist), tauschen aber nichts aus und kehren dann zurück. Die beste Laufzeiteffizienz ist also \(O (n)\).

  • Der schlimmste Fall ist ein Array, das in absteigender Reihenfolge sortiert ist. Jedes Element muss die volle Entfernung zu seiner richtigen Stelle „blasen“, so dass wir niemals vorzeitig beenden werden (aufgrund von sorted ) und die Bedingung in der if Anweisung wird jedes Mal wahr sein, also werden wir so viele Swaps wie nötig durchführen. Wenn wir die Summe berechnen, erhalten wir

    $$\sum_{j = 1}^n (n – j) = n – \sum_{j = 1}^n j$$

    wobei sich die zweite Summe zu \(\frac{n(n+1)}{2}\), geben Sie uns eine Reihenfolge von \(O (n)\).

Korrektheit der Blasensortierung

Wenn wir die Korrektheit der Blasensortierung wie üblich beweisen wollen, kommt es darauf an, die richtigen Invarianten auszuwählen. Hier ist es hilfreich, wenn wir zwei haben, eine von jeder Schleife:

template<typename T>void bubble_sort(vector<T>& data) { for(int j = 1; j < data.size(); ++j) { bool sorted = true; for(int i = 0; i < data.size() - j; ++i) if(data.at(i) > data.at(i + 1)) { swap(data.at(i), data.at(i + 1)); // INVARIANT: every element in data to data is *smaller* // than data. sorted = false; } // INVARIANT: every element of data to data is smaller // than data, and every element of data to // data is larger than data. (That is, // data is in the right place.) if(sorted) return; }}

Einfügesortierung

Angenommen, wir teilen die Eingabe in zwei „Abschnitte“ auf, sortiert und unsortiert. Der sortierte Abschnitt ist zunächst leer. Für jedes Element im unsortierten Abschnitt fügen wir es in der richtigen sortierten Position in den sortierten Abschnitt ein. Da dies ein Array / Vektor ist, müssen beim Einfügen eines Elements alle Elemente um einen Schritt nach oben verschoben werden. Obwohl wir eine Version davon erstellen können, die „an Ort und Stelle“ arbeitet, auf einem einzelnen Array (denn wenn die sortierte Region um 1 wächst, schrumpft die nicht sortierte Region um 1, so dass die Gesamtgröße immer n ist), wird es seineinfacher zu verstehen, wenn wir es als Funktion schreiben, die Elemente von einem nicht sortierten Vektor in einen sortierten Vektor verschiebt, der dann zurückgegeben wird.

Die Einfügesortierung ist stabil.

template<typename T>vector<T> insertion_sort(vector<T>& data) { vector<T> sorted; for(int i = 0; i < data.size(); ++i) { T& item = data.at(i); // Find the proper place for item in sorted int pos = sorted.size(); // Defaults to the end for(int j = 0; j < sorted.size(); ++j) if(sorted.at(j) >= item) { pos = j; break; } // Insert the item at pos, by shifting everything forward // (Increases the size of sorted by 1) sorted.insert(sorted.begin() + pos, item); }}

Was sind die besten und schlechtesten Fälle für diesen Algorithmus? Es ist ein bisschen schwierig, es herauszufinden, da die Komplexität von insert proportional zur Anzahl der bewegten Elemente ist (dh zu sorted.size() - pos). Während also die Schleife, um die Position zu finden, vorzeitig beendet werden kann (sogar in der ersten Iteration), ist dies schlecht für die Einfügung, da dies impliziert, dass pos klein und damit die Laufzeit von insert ziemlich schlecht ist. Auf der anderen Seite, wenn die innere Schleife bis zum Ende läuft (pos = sorted.size()), dann macht die insert effektiv nichts anderes als eine push_back .

In der Tat balancieren sich die innere Schleife und die insert immer gegenseitig aus, so dass diesumme zwischen ihnen ist sorted.size(). Und sorted.size() nimmt um eins zujedes Mal durch die äußere Schleife, also haben wir wieder unsere „dreieckige“ Schleife.

Wir können eine rekursive Version mit Hilfe eines Dienstprogramms schreiben Funktionen:

  • insert platziert ein Element an der richtigen Stelle im sortierten Bereich, indem alles nach oben verschoben wird.

Wenn diese beiden vorhanden sind, wird die rekursive Implementierung

template<typename Iterator>void insertion_sort(Iterator start, Iterator unsorted, Iterator finish) { if(start == finish - 1) return; // One element else { // Insert first unsorted element into sorted region insert(start, unsorted, *unsorted); // Recursively sort the remainder of the unsorted region. insertion_sort(start, unsorted+1, finish); }}

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.