Algorithmen II

Sortieralgorithmen

Sortieralgorithmen dienen zum Sortieren von Elementen in einem Bereich. Für den Vergleich der Elemente wird, wenn nichts anderes erwähnt, das Predicate less{} verwendet.

iter sort (ITER_RNG irng, BPRED cmp={}, PROJ prj={});

Sortiert die Elemente im Bereich irng und liefert einen Iterator auf das Ende des Bereichs zurück. Die Reihenfolge bei gleichwertigen Elementen ist nicht definiert. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 vor val2 einzusortieren ist.

iter stable_sort (ITER_RNG irng, BPRED cmp={}, PROJ prj={});

Wie sort(), jedoch wird die Reihenfolge bei gleichwertigen Elementen nicht verändert.

iter partial_sort (iter first, iter middle, iter last, BPRED cmp={}, PROJ prj={});
iter partial_sort (RANGE rng, iter middle, BPRED cmp={}, PROJ prj={});

Sortiert die Elemente im Bereich [first...last) bzw. rng so, dass im Bereich [first...middle) bzw. [rng.begin()...middle)) die kleineren Werte zu liegen kommen. Die Reihenfolge der restlichen Elemente [middle...last) bzw. [middle...rng.end()) ist nicht definiert. Als Rückgabewert liefert die Funktion einen Iterator auf das Ende des Bereichs. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 vor val2 einzusortieren ist.

#include <print>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> lobj {11,33,22,44,66,4,8,7};
    // Vektor an an 5. Stelle aufteilen (Wert: 66)
    std::ranges::partial_sort(lobj, lobj.begin()+4);
    for (auto& elem : lobj)
        std::print("{},", elem);
}

4,7,8,11,66,44,33,22,

riter partial_sort_copy (ITER_RNG irng1, ITER_RNG irng2, BPRED cmp={}, PROJ prj={});

Kopiert und sortiert die Elemente aus dem Bereich irng1 in den Bereich irng2. Die Anzahl der kopierten Daten wird durch den kleineren der beiden Bereiche bestimmt. Als Rückgabewert liefert die Funktion eine Struktur vom Typ partial_sort_copy. Das Member in verweist auf das Ende des Bereichs irng1 und das Member out auf das Ende der kopierten Elemente im Bereich irng2. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 vor val2 einzusortieren ist.

bool is_sorted (ITER_RNG irng, BPRED cmp ={}, PROJ prj={});

Liefert true zurück, wenn die Elemente im Bereich irng sortiert sind. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

sort_01:

Die Datei mitglieder.txt enthält die Mitgliederliste eines Vereins. Für jedes Mitglied ist dessen Name sowie das Eintrittsdatum abgelegt.

Uwe Schmidt, 01.07.2013
Hans Mueller, 22.04.2010
Gabi Mueller, 22.04.2010
Gustav Lehmann, 01.03.2011
Xaver Glueck, 01.01.2010
Hannelore Schmid, 13.05.2014

Lesen Sie die Mitgliederliste ein und geben sie aus. Sortieren Sie die Mitgliederliste nach Eintrittsdatum und geben die sortierte Liste erneut aus.

Mitgliederliste unsortiert:
Uwe Schmidt, 01.07.2013
Hans Mueller, 22.04.2010
Gabi Mueller, 22.04.2010
Gustav Lehmann, 01.03.2011
Xaver Glueck, 01.01.2010
Hannelore Schmid, 13.05.2014

Mitgliederliste sortiert:
Xaver Glueck, 01.01.2010
Gabi Mueller, 22.04.2010
Hans Mueller, 22.04.2010
Gustav Lehmann, 01.03.2011
Uwe Schmidt, 01.07.2013
Hannelore Schmid, 13.05.2014

Mengenalgorithmen

Die Mengenalgorithmen dienen zum Berechnen von gleichwertigen bzw. unterschiedlichen Elementen in zwei Bereichen (Mengen). Beide Bereiche müssen aufsteigend sortiert sein.

bool includes (ITER_RNG irng1, ITER_RNG irng2, BPRED cmp={}, PROJ prj={});

Vergleicht, ob für alle Elemente des Bereichs irng1 gleichwertige Elemente im Bereich irng2, unter Beachtung der Reihenfolge, vorhanden sind. Die Funktion liefert true zurück, wenn alle Elemente in irng2 ebenfalls in irng1 enthalten sind. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

set_union_result set_union (ITER_RNG irng1, ITER_RNG irng2, iter dest, BPRED cmp={}, PROJ prj={});

Erzeugt aus den Elementen im Bereich irng1 und irng2 die Vereinigungsmenge, d.h. die Menge der Elemente, die in irng1 oder irng2 enthalten sind. Die Vereinigungsmenge wird ab der Position dest abgelegt. Als Rückgabewert liefert die Funktion eine Struktur vom Typ set_union_result. Die Member in1 und in2 verweisen auf das Ende von irng1 bzw. irng2. Das Member out verweist auf das Ende der Vereinigungsmenge im Bereich dest. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

set_difference_result set_difference (ITER_RNG irng1, ITER_RNG irng2,
                                                             iter dest, BPRED cmp={}, PROJ prj={});

Erzeugt aus den Elementen im Bereich irng1 und irng2 die Differenzmenge, d.h. die Menge der Elemente, die in irng1 enthalten sind aber nicht in irng2. Die Differenzmenge wird ab der Position dest abgelegt. Als Rückgabewert liefert die Funktion eine Struktur vom Typ set_difference_result. Das Member in verweist auf das Ende von irng1. Das Member out verweist auf das Ende der Differenzmenge im Bereich dest. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

set_symetric_differenct_result set_symetric_difference (ITER_RNG rng1, ITER_RNG rng2, iter dest, BPRED cmp={}, PROJ1 prj1={}, PROJ2 prj2={});

Erzeugt aus den Elementen im Bereich irng1 und irng2 eine symmetrische Differenzmenge, d.h. die Menge der Elemente, die nur in einem der Bereiche enthalten sind. Die Differenzmenge wird ab der Position dest abgelegt. Als Rückgabewert liefert die Funktion eine Struktur vom Typ set_symetric_difference_result. Die Member in1 und in2 verweisen auf das Ende von irng1 bzw. irng2. Das Member out verweist auf das Ende der Differenzmenge im Bereich dest. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

set_intersection_result set_intersection (ITER_RNG irng1,ITER_RNG irng2, iter dest,
                                                                  BPRED cmp={}, PROJ1 prj1={}, PROJ2 prj2={});
oiter set_intersection (iiter1 first1, iiter1 last1, iiter2 first2, iiter2 last2,
                                      oiter d_first, BPRED cmp);

Erzeugt aus den Elementen im Bereich irng1 und irng2 die Schnittmenge, d.h. die Menge der Elemente, die in irng1 und in irng2 enthalten sind. Die Schnittmenge wird ab der Position dest abgelegt. Als Rückgabewert liefert die Funktion eine Struktur vom Typ set_intersection_result. Die Member in1 und in2 verweisen auf das Ende von irng1 bzw. irng2. Das Member out verweist auf das Ende der Schnittmenge im Bereich dest. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

#include <print>
#include <algorithm>
#include <vector>

int main()
{
    // 2 Ausgangsmengen
    std::vector<int> vect1 {1,2,3,4,5};
    std::vector<int> vect2 {1,1,4,5};
    // Ergebnismenge
    std::vector<int> resVect;

    // Vereinigungsmenge
    std::ranges::set_union(vect1, vect2,
                   std::back_inserter(resVect));
    std::println("set_union:");
    for (auto elem: resVect)
        std::print("{},",elem);

    // Ergebnismenge leeren
    resVect.clear();
    // Differenzmenge
    std::ranges::set_difference(vect1, vect2,
                        std::back_inserter(resVect));
    std::println("\nset_difference:");
    for (auto elem: resVect)
        std::print("{},",elem);

    // Ergebnismenge leeren
    resVect.clear();
    // Schnittmenge
    std::ranges::set_intersection(vect1, vect2,
                        std::back_inserter(resVect));
    std::println("\nset_intersection:");
    for (auto elem: resVect)
        std::print("{},",elem);
    std::println("");
}

set_union:
1,1,2,3,4,5,
set_difference:
2,3,
set_intersection: 1,4,5,

Übungen

menge_01:

Ein Verein für Handball und Fußball führt für jede Sportart eine Spielerliste:

// Handballspieler
std::vector<std::string> handball
{ "Franz Mueller"s,"Gustav Maier"s,"Uwe Lehmann"s,
  "Adrian Schmid"s,"Sabine Krause"s,"Gisela Schmid"s };
// Fussballspieler
std::vector<std::string> fussball
{ "Adrian Schmid"s,"Xaver Bauer"s,"Klaus Maier"s,
  "Gustav Lehmann"s, "Sabine Krause"s };

Als Spielwart ist es Ihre Aufgabe, eine Liste der Spieler zu erstellen, die nur eine der beiden Sportarten betreibt, und eine zweite Liste der Spieler, die beide Sportarten betreiben.

Personen die nur Handball oder Fussball spielen:
Franz Mueller
Gisela Schmid
Gustav Lehmann
Gustav Maier
Klaus Maier
Uwe Lehmann
Xaver Bauer

Personen die sowohl Handball wie auch Fussball spielen:
Adrian Schmid
Sabine Krause

Permutationsalgorithmen

Permutationsalgorithmen berechnen mögliche Kombination von Elementen. So können z.B. die Buchstaben ABC wie folgt kombiniert werden:

ABC, ACB, BAC, BCA, CAB, CBA

next_permuation_result next_permutation (ITER_RNG irng, BPRED cmp={}, PROJ prj={});

Liefert die nächste Permutation der Elemente im Bereich irng. Als Rückgabewert liefert die Funktion eine Struktur vom Typ next_permutation_result. Das Member in verweist auf das Ende von irng. Das Member found ist true, wenn eine neue Permutation berechnet werden konnte und false, wenn alle Permutationen berechnet sind. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1 kleiner val2 ist.

prev_permutation_result prev_permutation (ITER_RNG irng, BPRED cmp={}, PROJ prj={});

Wie next_permuation(), nur wird die vorhergehende Permutation erneut berechnet.

bool is_permutation (ITER_RNG irng1, ITER_RNG irng2, BPRED cmp={},
                                    PROJ1 prj1={}, PROJ2 prj2={});

Liefert true zurück, wenn der Bereich irng1 eine Permutation des Bereichs irng2 ist. Der Vergleich erfolgt mit dem Predicate bool cmp(DTYP val1, DTYP val2). Es liefert true zurück, wenn val1==val2 ist. Standardmäßig erfolgt der Vergleich mit dem Predicate equal_to{}.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <array>
using namespace std::string_literals;

int main()
{
    // Array mit den Farben
    std::array<std::string,3> farben
    {
        "rot"s,"gelb"s,"gruen"s
    };
    // Array vorher sortieren
    std::ranges::sort(farben);

    // Alle Permutationen der 3 Farben berechnen
    do
    {
        std::ranges::copy(farben,
             std::ostream_iterator<std::string>
               (std::cout,", "));
        std::cout << '\n';
    } while (std::ranges::next_permutation(farben).found);
}

gelb, gruen, rot,
gelb, rot, gruen,
gruen, gelb, rot,
gruen, rot, gelb,
rot, gelb, gruen,
rot, gruen, gelb,

Numerische Algorithmen

Für die nachfolgenden numerischen Algorithmen gibt es keine Varianten, die für die zu verarbeitenden Bereiche Ranges anstelle von Iteratoren verwenden. Aus diesem Grund liegen alle nachfolgend aufgeführten numerische Algorithmen im Namensraum std und nicht im Namensraum std::ranges und es ist die Header-Datei numeric einzubinden.

void iota (iter first, iter last, DTYP val);

Füllt den Bereich [first...last) mit aufsteigenden Werten, beginnend mit dem Wert val.

DTYP accumulate (iter first, iter last, DTYP init);
DTYP accumulate (iter first, iter last, DTYP init, BFUNC func);

Summiert die Werte im Bereich [first...last) auf, wobei die Summe mit dem Wert init vorbelegt wird. Die erste Form verwendet für die Summenbildung den Operator + und die zweite Form die Funktion DTYP func(DTYP val1, DTYP val2). Als Returnwert liefert func das Ergebnis aus der Operation mit den beiden Parametern.

iter partial_sum (iter first, iter last, iter dest); iter partial_sum (iter first, iter last, iter dest, BFUNC func);

Berechnet aus den Werten im Bereich [first..last) die Teilsummen und legt diese ab der Position dest ab. Die Berechnung der Teilsummen erfolgt nach folgendem Schema:

*dest = *first;
*(dest+1) = *(dest) + *(first+1);
*(dest+2) = *(dest+1) + *(first+2);
usw.

Als Returnwert liefert die Funktion einen Verweis auf das nächste Element nach den berechneten Teilsummen. Die erste Form verwendet für die Summenbildung den Operator + und die zweite Form die Funktion DTYP func(DTYP val1, DTYP val2). Als Returnwert liefert func das Ergebnis aus der Operation mit den beiden Parametern.

iter adjacent_difference (iter first, iter last, iter dest); iter adjacent_difference (iter first, iter last, iter dest, BFUNC func);

Berechnet die Differenz zwischen den Elementen im Bereich [first...last) und legt diese ab Position dest ab. Als Returnwert liefert die Funktion einen Verweis auf das nächste Element nach den berechneten Differenzen. Die erste Form verwendet für die Differenzbildung den Operator - und die zweite Form die Funktion DTYP func(DTYP val1, DTYP val2). Als Returnwert liefert func das Ergebnis aus der Operation mit den beiden Parametern.

#include <iostream>
#include <print>
#include <numeric>
#include <iterator>
#include <array>
using namespace std::string_literals;

int main()
{
    // Array mit fortlaufenden Werten initialsiieren
    std::array<int,5> data;
    std::iota(data.begin(), data.end(), 1);

    std::println("Arrayinhalt:");
    std::copy (data.begin(), data.end(),
               std::ostream_iterator<int>(std::cout,", "));

    // Summe der Werte im Array berechnen
    auto sum = std::accumulate(data.begin(), data.end(),0);
    std::println("\nSumme der Array-Elemente: {}", sum);

    // Produkt der Werte im Array berechnen
    sum = std::accumulate(data.begin(), data.end(), 1,
                          [] (int val1, int val2)
                             { return val1*val2;} );
    std::println("Produkt der Array-Elemente: {}", sum);

    // Differenz der Array-Wert im Vector ablegen
    std::print"Differenzen der Array-Elemente: ";
    std::vector<int> resVect;
    std::adjacent_difference(data.begin(), data.end(),
                             std::back_inserter(resVect));
    std::copy (resVect.begin(), resVect.end(),
               std::ostream_iterator<int>(std::cout,", "));
}

Arrayinhalt:
1, 2, 3, 4, 5,
Summe der Array-Elemente: 15
Produkt der Array-Elemente: 120
Differenzen der Array-Elemente: 1, 1, 1, 1, 1,