Bubblesort mit Funktion (C++)

[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

[Ein ehemaliger Benutzer]

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.

[EinNutzer0]

@Swordfish Naja, gute Algorithmen sind ja nicht deswegen "gut", weil sie möglichst genau der menschlichen Intuition folgen... eher im Gegenteil sind diese dann schlechter.

[Swordfish]

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

gute Algorithmen

da sprach ich von Neulingen, da ist Nachvollziehbar und intuitiv > Effizienz.

[Leon0402]

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

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

Hmm aber auch bei Vorsortierung ist insertionSort eigentlich schneller (oder zumindest gleich schnell), oder nicht?

[hustbaer]

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

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

Quicksort und Mergesort

kenne ich nicht

Was dich irgendwie schon für weitere Diskussion disqualifiziert.

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

Korrekt. Das ist bei den meisten Sachen so.

Als Lehrbeispiel bleibt es trotzdem mindestens grenzwertig.

Weil?

Zeig' mir mal einen der ein Kartenspiel intuitiv mit Bubblesort sortiert. Viel Glück.

Und?

[Swordfish]

@hustbaer Können wir uns darauf einigen daß wir uns nicht einigen können?

[EinNutzer0]

Los, holt die Knüppel raus und haut euch auf die Rübe... Nur weil eine Anfängerfrage gestellt wurde

[hustbaer]

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