Bubblesort mit Funktion (C++)

DocShoe

@zeropage
Ja, der hat mir auch gut gefallen, zumindest die Sachen, die ich gesehen habe.

Swordfish

@DocShoe @wob Die beiden zitierten Header gibt es auch in C++. Aber die heißen geringfügig anders und packen ihr Zeugs auch nach std. Das war mein Punkt.

EinNutzer0

Hier wär die C++-Variante (ohne das Einlesen, vielleicht ginge es noch einfacher):

#include <cstdlib>
#include <iostream>

size_t bs(const size_t len, int *const a)
{
    size_t i, j;
    bool conti = true;
    for (i = 0; conti; i++)
    {
        conti = false;
        for (j = 0; j < len - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                conti = true;
                std::swap(a[j], a[j + 1]);
            }
        }
    }
    return i;
}

int main(int argc, char **argv)
{
    int a[][5] = {{1, 2, 3, 4, 5}, {5, 4, 3, 2, 1}};
    size_t len = sizeof(a[0]) / sizeof(int);

    std::cout << bs(len, a[0]) << std::endl;
    for (int i : a[0])
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;

    std::cout << bs(len, a[1]) << std::endl;
    for (int i : a[1])
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

Edit: Und noch eine generische Variante:

#include <cstdlib>
#include <iostream>
#include <functional>

template <class T>
size_t bs(const size_t len, T *const a, const std::function<bool(const T &, const T &)> c)
{
    size_t i, j;
    bool conti = true;
    for (i = 0; conti; i++)
    {
        conti = false;
        for (j = 0; j < len - 1 - i; j++)
        {
            if (c(a[j], a[j + 1]))
            {
                conti = true;
                std::swap(a[j], a[j + 1]);
            }
        }
    }
    return i;
}

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

    std::cout << bs<float>(len, a[0], compare) << std::endl;
    for (int i : a[0])
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;

    std::cout << bs<float>(len, a[1], compare) << std::endl;
    for (int i : a[1])
    {
        std::cout << i << ", ";
    }
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

Swordfish

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

Kennst du vielleicht eine Website, ein Video oder sonstiges Lehrmaterial, die dieses Thema gut erklären?

Was ich Dir vorher durch die Blume sagen wollte bringt @hustbaer hier gut auf den Punkt:

@hustbaer sagte in Anfänger - Programm funktioniert, aber....:

C++ ist halt ne ziemliche Sau, da stimme ich @Mechanics voll zu. Gründe dafür gibt es einige. Der ganze ranzige Legacy-Kram der von C übernommen wurde, [...]
Eines der grossen Probleme dabei ist dass du in C++ so viele Dinge machen kannst die "funktionieren" (bzw. zu funktionieren scheinen), aber totaler Quatsch sind oder sogar einfach nur falsch. Schlimmer noch: Viele Tutorials sind von Anfängern oder Stümpern geschrieben und bis zum Rand voll mit Fehlern. Dummerweise kannst du als Anfänger das aber nicht riechen.

Swordfish

@EinNutzer0 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. Das return EXIT_SUCCESS ist sowas von unnötig. Dann schreibst Du noch explizit C++ und machst dann

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

    size_t i, j;

wozu?? Lass das!

Wenn Du sowieso schon ein Template schreibst, dann lass std::function sein. Und in neuem Code für Noobs West-side-const zu verwenden ist auch ...

</rant>

EinNutzer0

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

Wenn Du sowieso schon ein Template schreibst, dann lass std::function sein

Da tritt leider ein Problem auf...

Ich kann zwar template <class T, typename Comparator> schreiben, aber dann wäre die Typsicherheit nicht mehr gegeben.

Bleib doch mal sachlich mit deiner Kritik...

Swordfish

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

Typsicherheit

ist in diesem Kontext eine eher unkonventionelle Aussage.

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

Bleib doch mal sachlich mit deiner Kritik...

Wo war ich unsachlitsch?

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