Bubblesort mit Funktion (C++)

Jockelx

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

Ich garantiere auch, dass nicht eine einzige Person bei der selbsterfundenen Lösung auf BS kommen wird

Das stimmt schonmal nicht. Meine erster Sortierung war so was wie Bubblesort und das war definitiv selbst ausgedacht (mangels Büchern oder sowas wie Internet).
Und Jahre später im Studium habe ich Bubblesort auch als den mit Abstand besten (im Sinne von verstehen und daran rumexperimtieren) empfunden.

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

Da hat man wenigstens Intuition beim Umsetzen und Verstehen.

Schön, dass du für die Menschheit sprichst; das scheint mir aber doch sehr subjektiv (umgekehrt pro bubblesort natürlich auch).

SeppJ

Wollen wir 100 Leute auf der Straße befragen? Oder wenn wir Statistiken sammeln wollen: Mein erster Programmierkurs, mit Variante 1: 100% der Leute (inklusive mir) ohne Vorwissen haben Selection/Insertionsort erfunden, die Bubblesorter waren 100% Leute, die das aus anderen Kursen hatten. Was dann auch gewissermaßen die These bestätigt, dass es die Leute verdirbt: Denn die Aufgabe war, so effizient wie möglich zu sortieren. Sie haben trotzdem Bubblesort genommen. Und das Wettrennen am Ende verloren. Und die Insertion/Selectionsorter waren schneller mit der Programmierung fertig, da einfacher.

Jockelx

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

Wollen wir 100 Leute auf der Straße befragen?

Wozu? Hast du doch schon längst gemacht! Oder wo auch immer du die Daten her hast, das "man" von selber nie auf Bubblesort kommt und das "man" das sowieso nicht intuitiv finden kann.
Leider war ich bei deiner Repräsentativen Umfrage nicht dabei. Hätte sonst das Ergebnis verfälscht

EinNutzer0

Können wir uns vielleicht darauf einigen: Er ist langsam, aber er ist für die Übung, den Einstieg und für theoretische Überlegungen gut?

Wenn ich ein Auto bauen möchte, beginne ich doch auch erstmal mitm BobbyCar, und nicht gleich mitm Porsche.

Quiche Lorraine

@EinNutzer0
Ich verstehe auch so langsam die Diskussion nicht mehr.

Warum macht man wegen dem Bubblesort so ein Fass auf? Was ist denn so schlimm an Bubblesort als das man deren Lehre verbietet? Warum muss denn ein Algorithmus praxisrelevanz haben?

Ich könnte genauso argumentieren dass man die Lehre von verketteten Listen verbietet.

Vor allen Dingen. Es handelt sich doch um Hintergrundwissen. In 99,9% aller Fälle wird man doch std::sort nutzen.

PS: Selbst Algorithmen wie Stoogesort haben eine Existenzberechtigung. Und sei es nur als Übung in der Komplexitätstheorie.

hustbaer

@SeppJ
Bubblesort ist einfach, weil es ausser Schleifen, Verlgeichen und Vertauschen nichts weiter benötigt. Das stimmt grundsätzlich auch für Insertionsort und Selectionsort. Nur Insertionsort bzw. Selectionsort "zu Fuss" zu implementieren, also ohne dass man fertige Funktionen für "in der Mitte einfügen" bzw. "in der Mitte entfernen" hat, ist mehr bzw. bestenfalls gleich viel Aufwand wie Bubblesort zu implementieren. Zumindest wenn man mit Arrays arbeitet. Und wenn man den Ball flach halten möchte, dann sollte man besser mit Arrays arbeiten.

Daher halt ich Bubblesort immer noch für einen guten Einstieg. Gut im Sinn von: is OK/nicht schlecht/nicht grundsätzlich abzulehnen/kann man ruhig so machen. Ich habe nie behauptet dass es ideal wäre.

Die BubbleSorter sind ja in der Bringeschuld, zu erklären, wieso das ein guter Einstieg ist.

Siehe oben.
Davon abgesehen sind beide gleichermassen in der Bringeschuld, der der behauptet dass es gut ist und der der behauptet dass es schlecht ist.

Was dann auch gewissermaßen die These bestätigt, dass es die Leute verdirbt: Denn die Aufgabe war, so effizient wie möglich zu sortieren. Sie haben trotzdem Bubblesort genommen. Und das Wettrennen am Ende verloren. Und die Insertion/Selectionsorter waren schneller mit der Programmierung fertig, da einfacher.

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.

Swordfish

@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.

Mechanics

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.

Leon0402

@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.

EinNutzer0

@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...

Leon0402

@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.

Jockelx

@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

EinNutzer0

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.

Leon0402

@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.

wob

@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 $\mathcal{O}(n)$ , aber der eine ist trotzdem wesentlich schneller. In der Praxis ist $n$ auch immer endlich, oft sogar im Bereich von 0 bis 10 (oder 100). Und zu untersuchen, wann $c_\text{klein} \times n^2$ größer wird als $c_\text{gross} \times n \log n$ , ist doch durchaus interessant.

yahendrik

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.

EinNutzer0

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

Swordfish

@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.

Jockelx

@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.

Swordfish

@Jockelx ich habe nichts Gegenteiliges gesagt.