Bubblesort mit Funktion (C++)

wob

Ich hätte andere Dinge zu kritisieren:

Der Funktionsname 'bs'. Waren die anderen Buchstaben aus? Klare Namen! Bs kann alles mögliche bedeuten. Zum Beispiel Stierexkrement... Was spricht gegen bubblesort?
Parameterübergabe mit pointer und size. (Hier sogar in der unüblichen Reihenfolge size und pointer). Das ist generell bäh, weil der caller die Größe bestimmen muss und man als Parameter einfach nur eine freie Zahl hat.
Bessere Optionen sind meiner Meinung nach folgende. Erstens es wie in der STL zu machen und 2 Iteratoren zu übergeben. Dann funktioniert das bubblesort nämlich genau wie das std::sort! Das sollte daher erste Wahl sein. Alternativ könnte man auch eine Referenz auf den ganzen zu sortierenden std::vector übergeben. Das ist dann ein sehr einfaches Interface. Ist aber nicht mehr generisch und man kann kene Teilbereiche mehr sortieren. Gerade so ein kleines Anfängerbeispiel sollte man so einfach wie möglich halten und möglicherweise auf Templates verzichten.
(Schließe mich der Kritik gegen die std::function hier an)

(@Swordfish: wo du unsachlich warst: bei der const side... ich mag west const deutlich lieber als east const, denke aber, dass das hier völlig irrelevant ist)

EinNutzer0

Es soll aber ein Array sortiert werden... Wäre es so besser? Problem, man kann die Arraylänge eines 2D-Arrays nicht in einer Funktion bestimmen:

#include <cstdlib>
#include <iostream>

template <class T, typename Comparator>
size_t bubblesort(T *const array, Comparator c, size_t len)
{
    size_t i, j;
    bool conti = true;
    std::cout << len << std::endl;
    for (i = 0; conti; i++)
    {
        conti = false;
        for (j = 0; j < len - 1 - i; j++)
        {
            if (c(array[j], array[j + 1]))
            {
                conti = true;
                std::swap(array[j], array[j + 1]);
            }
        }
    }
    return i;
}

int main(int argc, char **argv)
{
    float a[2][5];
    auto greater = [](float x, float y) -> bool { return x > y; };
    for (size_t i = 0; i < 2; i++)
    {
        for (size_t j = 0; j < 5; j++)
        {
            a[i][j] = rand() % 20;
        }
    }

    std::cout << bubblesort(a[0], greater, 5) << std::endl;
    for (int i : a[0])
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;

    std::cout << bubblesort(a[1], greater, 5) << std::endl;
    for (int i : a[1])
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

Ich vermute, die Dimensionsinformationen von a sind in bubblesort nicht mehr sichtbar.

Selbstverständlich wäre mit vector alles besser, aber der TE soll doch Arrays sortieren.

Th69

Und wo ist das Problem bei einer Funktion mit Iteratoren das Array zu übergeben?

bubblesort(array, &array[N]);
// bzw.
bubblesort(begin(array), end(array));

*john 0

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

Und wo ist das Problem bei einer Funktion mit Iteratoren das Array zu übergeben?

Der Designfehler bei einem Interface mit Iteratoren besteht darin, dass die Iteratoren nicht zu einem Container gehören müssen. Dieser Umstand ist zwar eine Voraussetzung, dass der Algorithmus funktioniert, dies kann aber nicht durch die Sprache erzwungen werden.

Dieser Beitrag wurde gelöscht!

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

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

Wo war ich unsachlitsch?

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

Und in neuem Code für Noobs West-side-const zu verwenden ist auch ...

hustbaer

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

Würdest Du Anti-Patterns vielleicht einmal bleiben lassen? stdout ist so gut wie überall line-buffered. Die ganzen std::endl sind sowas für die Katz' - ein stinknormales Newline tuts auch.

Najaaaa...
Also wir haben z.B. Unit-Tests die auf stdout rausschreiben. Ab und an baut mal jemand Mist, und dann crasht ein Test. Und dann ist es halt doof, wenn im Log-Output die hälfte fehlt, weil stdout halt nicht mehr line-buffered ist wenn man es in ein File umleitet.
(Also das Test-Framework flusht schon brav seine Meldungen, d.h. man weiss natürlich welcher Test gecrasht ist. Aber wenn der Test ein paar "progress" Meldungen ausgibt, und dabei nicht flusht, dann weiss man halt nicht wo genau es den Test zerrissen hat.)

Also ich würde sagen: wenn man Log-/Fehlermeldungen ausgibt, dann finde ich std::endl angebracht. Wenn man Daten ausgibt, speziell wenn es sich potentiell um grosse Datenmengen handelt, dann lieber einfach nur \n.

Und bei Meldungen eines interaktiven Programms wie hier...
Also wenn das Programm nur sinnvoll zu verwenden ist wenn die Meldung auch früh genug angezeigt wird, dann würde ich auch hier std::endl verwenden. Einfach weil nicht flushen dann keinen Sinn macht. Interaktive SSH Sessions & Co sollten zwar soweit ich weiss zu isatty = true und damit zu line-buffered stdout führen. Aber wenn man so googelt bekommt man den Eindruckt dass das nicht immer so ganz zu funktionieren scheint.
(EDIT: OK, ist doch kein Problem - siehe Beitrag von @Swordfish)

EinNutzer0

Das gefällt mir schon besser.

#include <cstdlib>
#include <iostream>

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

int main(int argc, char **argv)
{
    const int n = 5;
    float a[2][n];
    auto greater = [](float x, float y) -> bool { return x > y; };
    for (size_t i = 0; i < 2; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            a[i][j] = (rand() % 20) / 5.0;
        }
    }

    std::cout << bubblesort(a[0], &a[0][n - 1], greater) << std::endl;
    for (float f : a[0])
    {
        std::cout << f << ", ";
    }
    std::cout << std::endl;

    std::cout << bubblesort(a[1], &a[1][n - 1], greater) << std::endl;
    for (float f : a[1])
    {
        std::cout << f << ", ";
    }
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

Bleibt immer noch die "Typunsicherheit" bei Comparator c...

Swordfish

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

Also wenn das Programm nur sinnvoll zu verwenden ist wenn die Meldung auch früh genug angezeigt wird, dann würde ich auch hier std::endl verwenden.

cout und cin sind tied

hustbaer

@Swordfish Touché
Das löst eventuelle Probleme mit interaktiven Programmen.
Löst aber nicht Probleme mit fehlenden Meldungen in stdout/stderr wenn ein Programm absemmelt

std::cerr wird automatisch geflusht.

Swordfish

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

Wäre es so besser?

Bubblesort sollte generell verboten und nicht mehr als Standartbeispiel für Sortieralgorithmen verwendet werden.

Leon0402

@Swordfish Warum?

Aus meiner Sicht ein sehr gutes Lehrbeispiel. Also für Komplexität (theoretische Informatik) nicht zum C++ lernen jetzt

Swordfish

@Leon0402 Bubble sort misconceptions aka why bubblesort shouldn't be taught

Th69

@Swordfish: Der Autor scheint aber nicht die verbesserte Variante (mit der Abfrage, ob das Array sortiert wurde) zu kennen, wenn man den Absatz "Bubble sort works well with data which is already almost sorted" so liest...

Leon0402

@Swordfish Wenn ich drüber nachdenke, ist da vermutlich was dran. Ja, man kann auch mit insertion sort anfangen und tatsächlich haben wir das auch so gemacht

Zum zitieren grade bei der Dikussion, was aus "Lehrsicht" Sinn macht, finde ich übrigens http://warp.povusers.org/grrr/bubblesort_eng.html besser

Quiche Lorraine

@Swordfish
Was ist so schlimm an Bubblesort?

Denn nicht alles was man gelehrt bekommt, hat auch später einen praktischen Nutzen. Ein Beispiel ist mir da noch lebhaft in Erinnerung: Implementierung einer Gleitkommadivision in Assembler ohne Nutzung von FPU Befehlen. Das war absolut fobar.

So manches erscheint mir nur Standardlehre oder Lückenfüller. Ohne nähergehenden Sinn.

Quiche Lorraine

@Swordfish
Wir durften unter anderem den Quicksort in Assembler, auf einer speziellen zweibändigen Turingmaschine oder unter eine obskuren Programmiersprache programmieren, welche nur die nötigsten Befehle kannte.

hustbaer

Bubblesort findet man sogar z.T. in realen Anwendungen, wo es auch Sinn macht.
Eben in diesen Nischen wo man passend vorsortierte Daten hat.

Gibt auch eine interessante Abwandlung davon (Cocktail Shaker Sort), wo man nicht immer in der selben Richtung durchgeht sondern so Knight-Rider-mässig immer die Richtung vor und zurück wechselt.

IMO ist das ein gutes Übungsbeispiel zum Einstieg. Man muss (und sollte) damit natürlich nicht Schluss machen. Quicksort und Mergesort sollte jeger mal gehört und verstanden haben wenn es um das Thema Sortieralgorithmen geht.

Swordfish

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

Quicksort und Mergesort

kenne ich nicht

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

Eben in diesen Nischen wo man passend vorsortierte Daten hat.

Ja, schön. Auch bei bestimmter Hardware kann es eine gute Lösung sein (Tape Drives). Aber das setzt voraus daß der betreffende welche genau weiß was er/sie/es tut. Als Lehrbeispiel bleibt es trotzdem mindestens grenzwertig. Zeig' mir mal einen der ein Kartenspiel intuitiv mit Bubblesort sortiert. Viel Glück.