3. Bubblesort mit Funktion (C++)

Bubblesort mit Funktion (C++)


  • @hustbaer sagte in Bubblesort mit Funktion (C++):

    @Swordfish Für mich heisst das übersetzt meistens so viel wie "ich hab keine Argumente mehr, aber will einfach trotzdem meine Meinung beibehalten".
    Ist jetzt aber auch nicht so dass das Thema besonders wichtig wäre. Also... ja, sicher.

    Ja, danke für die Blumen. Vielleicht habe ich einfach keine Lust darauf? Es ist ziemlich klar daß hier bestehende verfestigte Meinungen jegliche Lust zum Umdenken untergraben. Das brauch' ich mir nicht geben. Jedem Tierchen sein Pläsierchen.

    0
  • M

    Ich finde Bubble Sort soweit eigentlich schon intuitiv. Das erinnert mich an ein Spiel, das ich als Kind hatte, vielleicht deswegen.

    Und wir hatten das bis vor paar Jahren sogar tatsächlich produktiv im Einsatz 😃 Keine Ahnung, wer damals warum auf die Idee gekommen ist, das einzubauen, und warum das dann keinen interessiert hatte.

    0
  • L

    @hustbaer sagte in Bubblesort mit Funktion (C++):

    Wenn Bubblesort die Leute verdirbt, dann muss das selbe auch für Selection- und Insertionsort gelten. Denn wer das als "effizienten" Sortieralgorithmus wählt, der wird damit wohl kaum mehr Glück haben als jemand der Bubblesort wählt. Denn effizient sind im allgemeinen Fall alle drei nicht.

    Eben nicht! Wobei, bei selection sort mag ich dir da noch zustimmen. Aber insertion sort ist sehr effizient bei vorsortierten listen und bei kleinen Listen. Außerdem ist er auch stabil.
    Entsprechend findet er Anwendung in Kombination mit divide & conquer Algorithmen für genau diese Anwendungszenarien.

    Für Bubble sort gibt es dagegen keinen einzigen mir bekannten use case (wo er auch entsprechend besser geeignet wäre als ein insertion sort).

    Also wenn es um ein entweder oder geht, sollte man vermutlich den insertion sort behandeln. Er ist intuitiv, praxisrelevant und ist bestens geeignet als Einführung in die Komplexität etc.
    Es spricht aber imo nichts dagegen beides zu behandeln. Gerade die Erkenntnis, warum der bubble sort so praxis irrelevant ist, ist doch sehr gut 😉 Und man muss ja Komplexitätsbestimmung auch etwas üben.

    0
    E
    J
     2 Antworten
  • E
    Gesperrt

    @Leon0402 Ohne Benchmarks für einen typischen Anwendungsfall der drei genannten Algorithmen wäre ich sehr vorsichtig mit der Bewertung, welcher schneller wäre.

    Bubblesort hat im best case die Laufzeit Theta(n), die anderen, würde ich spontan sagen, nicht.

    Außerdem sind Speicherplatzanforderungen auch unter die Lupe zu nehmen. Es soll ja "Geräte" mit nur sehr wenig Speicher geben...

    0
  • L

    @EinNutzer0 InsertionSort hat als Best Case auch O(n), tritt ein, wenn das Array sortiert ist (also genauso wie beim bubble sort). Klar kann man auch einen bubblesort zusammen mit Merge sort verwenden ... ich sehe aber nicht, wo er besser sein sollte als insertion sort. Im Allgemeinen ist auch nahe des best case der insertion sort besser (um konstanten Faktor) afaik.

    Die Speicherplatzanforderungen verstehe ich nicht? Beide arbeiten in-place.

    0
  • J

    @Leon0402 sagte in Bubblesort mit Funktion (C++):

    Es spricht aber imo nichts dagegen beides zu behandeln

    Aber genau darüber herrscht doch Uneinigkeit!?
    Wir haben 2 praxisferne Algorithmen (wobei man sowie schon mal fragen muss, wann man in der Praxis selber Sortieralgorithmen schreibt) und von dem einen wird behauptet, dass er den Geist so vernebelt, dass der Lernende so verwirrt wird, dass er ihn auch in der Praxis einsetzen wird, nicht intuitiv ist, 100 Leute auf der Strasse ihn sowieso total doof finden, usw..,
    während der andere praxisuntägliche Algorithmus diese Eigenschaften auf magische Weise nicht hat.

    Ich habe mich hier nur beteiligt, weil komplett subjektives Empfinden (im Gegensatz zu meinem subjektiven Empfinden) hier als irgendwie wissenschaftlich belegt dargestellt wurde. Zwar dem Zeitgeist entsprechend, aber das muss ja nicht überall Einzug halten 😉

    0
  • E
    Gesperrt

    Hier sind einmal alle drei Sortieralgorithmen:

    #include <cstdlib>
#include <iostream>

template <class T, typename Comparator>
void bubble_sort(T *first, T *second, Comparator c)
{
    size_t len = std::distance(first, second) + 1;
    bool conti = true;
    for (size_t i = 1; conti; i++)
    {
        conti = false;
        for (size_t j = 0; j < len - i; j++)
        {
            if (c(first[j], first[j + 1]))
            {
                conti = true;
                std::swap(first[j], first[j + 1]);
            }
        }
    }
}

template <class T, typename Comparator>
void selection_sort(T *first, T *second, Comparator c)
{
    size_t len = std::distance(first, second) + 1;
    for (size_t i = 0; i < len; i++)
    {
        T min = first[i];
        size_t min_idx = i;
        for (size_t j = i + 1; j < len; j++)
        {
            if (c(min, first[j]))
            {
                min = first[j];
                min_idx = j;
            }
        }
        if (i != min_idx)
        {
            std::swap(first[i], first[min_idx]);
        }
    }
}

template <class T, typename Comparator>
void insertion_sort(T *first, T *second, Comparator c)
{
    size_t len = std::distance(first, second) + 1;
    for (size_t i = 1; i < len; i++)
    {
        T t = first[i];
        size_t j = 0;
        for (; j < i; j++)
        {
            if (c(first[j], t))
            {
                break;
            }
        }
        if (i != j)
        {
            for (; j < i; j++)
            {
                std::swap(first[j], first[i]);
            }
        }
    }
}

int main(int argc, char **argv)
{
    auto greater = [](int x, int y) -> bool { return x > y; };
    void (*fs[])(int *first, int *second, bool (*c)(int x, int y)) = {bubble_sort, selection_sort, insertion_sort};
    const size_t len = sizeof(fs) / sizeof(void *);
    for (size_t i = 0; i < len; i++)
    {
        int a[] = {5, 4, 6, 1, -50, -60, 10, 11, 9, 0};
        const size_t n = sizeof(a) / sizeof(int);
        fs[i](&a[0], &a[n - 1], greater);
        for (size_t j = 0; j < n; j++)
        {
            std::cout << a[j] << std::endl;
        }
        std::cout << std::endl;
    }
    return EXIT_SUCCESS;
}

    Jetzt müsste bitte noch jemand einen Benchmark-Test mit 10.000 Elementen (oder mehr) schreiben, da bin ich nicht firm drin. 😅

    0
    L
     1 Antwort
  • L

    @EinNutzer0 sagte in Bubblesort mit Funktion (C++):

    Jetzt müsste bitte noch jemand einen Benchmark-Test mit 10.000 Elementen (oder mehr) schreiben, da bin ich nicht firm drin

    Warum?

    Das ist eine theoretische Fragestellung, da ist erstmal kein Code für notwendig und auch kein Benchmark. Zum Beispiel selection sort ist immer O(n^2) von daher schon direkt ausgeschieden.

    Allgemein kommen beide Algorithmen auch nur in Frage für hybride Algorithmen. Daher kommt es eh vermutlich auf den konkreten anderen Algo an. Mir bekannt ist allerdings immer nur, dass insertion sort für hybride genutzt werden. Das wird vermutlich mal jemand berechnet haben, dass auch im best case insertion sort konstant besser ist.

    0
    W
     1 Antwort
  • W

    @Leon0402 sagte in Bubblesort mit Funktion (C++):

    Warum?

    Weil die Größenordnung ja nur die halbe Wahrheit ist. Ein Algorithmus brache z.B. 10 Sekunden pro Element, ein anderer 1 ns pro Element. Beide sind O(n)\mathcal{O}(n), aber der eine ist trotzdem wesentlich schneller. In der Praxis ist nn auch immer endlich, oft sogar im Bereich von 0 bis 10 (oder 100). Und zu untersuchen, wann cklein×n2c_\text{klein} \times n^2 größer wird als cgross×nlognc_\text{gross} \times n \log n, ist doch durchaus interessant.

    1
  • Y

    Je nach Datensatz und Größe der zu sortierenden Elemente kann es schon zu einigen Verschiebungen kommen.
    Ich habe das mal mit einigen Sorts mit 30.000 Elementen, die aus einem int als Vergleich und 5 doubles bestehen, durchgeführt.
    Falls es jemanden interessiert:

    https://i.imgur.com/zr423d2.png

    Links alle Sorts in immer der gleichen Reihenfolge, in der Mitte von langsam nach schnell die langsamen Sorts, rechts aufsteigend die schnellen.
    Rechts ist das ungefilterte Diagramm mit dem Datensatz.

    Zumindest sorteren alle richtig, das wurde überprüft. Bis auf den Introsort und den Intro/Merge sind alle von der Stange. Der Intro/Merge erstellt 2 Threads, die wiederum je 2 Threads starten und auf beiden Seiten einen Introsort durchführen, bevor die beiden Stränge zusammengeführt werden.
    Das gleiche passiert anschließend mit den verbleibenden beiden Strängen.

    Edit: Hier noch mal mit weniger Elementen, dafür aber wesentlich größeren Strukturen (kein pod):

    https://i.imgur.com/frG8Clw.png

    Wie abzusehen war, schneidet der Selectionsort besser ab.

    1
  • E
    Gesperrt

    Schweifen wir nicht ein bisschen von der ursprünglichen Frage ab? 😉 Wir sind ja schon bei allgemeinen, theoretischen Überlegungen aller Algorithmen dieser Kategorie... 😃

    0 1 Antwort

  • @EinNutzer0 sagte in Bubblesort mit Funktion (C++):

    Schweifen wir nicht ein bisschen von der ursprünglichen Frage ab?

    Das hat hier Tradition. Die Frage des OP sollte hinlänglich beantwortet sein.

    0
    J
     1 Antwort
  • J

    @Swordfish sagte in Bubblesort mit Funktion (C++):

    Das hat hier Tradition

    Ist doch aber auch okay, sobald die Frage beantwortet wurde. Kommt ja häufig auch ne interessante Diskussion bei rum.

    0 1 Antwort

  • @Jockelx ich habe nichts Gegenteiliges gesagt.

    0
array 25 funktionen 9 bubblesort 1 sortieren 1
Anmelden zum Antworten