Bubblesort mit Funktion (C++)

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.