3. Sortieralgorithmus BubbleSort

Sortieralgorithmus BubbleSort

  • S

    EOutOfResources schrieb:

    Sorex schrieb:

    ziemlich fähiger Mann

    Er soll euch lieber Iteratoren lehren statt einen std::vector zu nutzen und dann mit rohen Zeigern herumzuhantieren. Und eine Tauschfunktion gibt es auch schon: std::swap

    Iteratoren stehen erst im nächsten Semester auf dem Plan.

    0
  • E

    Das ist das was CStoll gesagt hat: Der Standard legt nicht fest, dass sich Iteratoren in rohe Zeiger konvertieren lassen.

    0
  • E

    Sorex schrieb:

    Iteratoren stehen erst im nächsten Semester auf dem Plan.

    Aha! Sequenzverarbeitung (in diesem Fall Sortierung) macht ihr schon aber Iteratoren nicht. Wer hat sich diesen Plan ausgedacht?

    0
  • C

    Wie gesagt - begin() und end() liefern Iteratoren. Die Adresse davon zu bilden ist möglicherweise zulässig (bin nicht 100% sicher), liefert aber nichts, was du als Zeiger verwenden könntest.

    0
  • S

    Ok, wird mir wohl erst klar, wenn ich verstehe wie Iteratoren funktionieren... ist das evtl. auch einer der Grüne, wehsalb sich der Vector mit dieser Funktion nicht richtig sortieren lässt?

    0
  • E

    Sorex schrieb:

    wehsalb sich der Vector mit dieser Funktion nicht richtig sortieren lässt?

    Jedenfalls nicht mit definiertem Verhalten. Und die Methode end() liefert im Normalfall sowieso keinen Iterator zurück den du durch durchiterieren eines Zeigers erhälst.

    0
  • 3

    Ruf ihn doch einfach so auf:

    bubbleSort(&vec[0], &vec[0] + vec.size());
    0
  • S

    Danke, aber wird so leider auch nicht richtig sortiert.

    6  15  16  20  18  20  4  10  12  8  //Ausgabe unsortiert
 8  20  6  15  20  16  10  12  18  4  //Ausgabe nach "Sortiervorgang"
    0
  • E

    Bist du dir sicher, dass das Sortierverfahren korrekt gecoded wurde?

    0
  • C

    Wenn ihr eh mit Pointern arbeitet, warum lasst ihr euch nicht von der C Standardbibliothek inspirieren?

    http://www.c-plusplus.net/forum/288649

    cooky451 schrieb:

    void bsort(void *arr, size_t n, size_t s, int (*comp)(const void*, const void*))
{
  int tmp;
  char *buf = (char*)malloc(s);
  if (!buf)
    return;
  do {
    tmp = 0;
    for (int i = s; i < n * s; i += s)
      if (comp((char*)arr + i - s, (char*)arr + i) > 0)
      {
        memcpy(buf, (char*)arr + i - s, s);
        memcpy((char*)arr + i - s, (char*)arr + i, s);
        memcpy((char*)arr + i, buf, s);
        tmp = 1;
      }
  } while(tmp);
  free(buf);
}

    Und ansonsten, was spricht eigentlich dagegen den Vektor gleich zu übergeben?

    void bsort(std::vector<int>& vec)
{
  int tmp;
  do {
    tmp = 0;
    for (int i = 1; i < vec.size(); ++i)
    {
      if (vec[i - 1] > vec[i])
      {
        tmp = vec[i - 1];
        vec[i - 1] = vec[i];
        vec[i] = tmp;
        tmp = 1;
      }
    }
  } while (tmp);
}

    (Geht bestimmt schöner mit Iteratoren :D)

    0
  • E

    Na ihr könntet doch gleich std::stable_sort aus <algorithm> nutzen.

    0
  • B

    Sorex schrieb:

    //Warum funktioniert an dieser Stelle folgender Aufruf nicht?..
    //bubbleSort(&field.begin(), &field.end()) -> Compiler meckert

    Das, was du suchst, ist field.front() und field.back() . Den unterschied zwischen diesen und begin() / end() erklärt dir die C++-Referenz deines Vertrauens.

    Prinzipiell schließ ich mich aber meinen Vorrednern an: Schön ist das nicht.

    0
  • C
    Mod

    Sorex schrieb:

    Danke, aber wird so leider auch nicht richtig sortiert.

    6  15  16  20  18  20  4  10  12  8  //Ausgabe unsortiert
 8  20  6  15  20  16  10  12  18  4  //Ausgabe nach "Sortiervorgang"

    Das ist kein Wunder, schließlich stellt die Zeigerversion auch keinen Bubblesort dar. Die enthaltenen Fehler sehen allerdings wie reine Tippfehler aus.

    0
  • M

    EOutOfResources schrieb:

    Sorex schrieb:

    ziemlich fähiger Mann

    Er soll euch lieber Iteratoren lehren statt einen std::vector zu nutzen und dann mit rohen Zeigern herumzuhantieren.

    Freu dich doch, dass immerhin std::vector benutzt wird.

    Und eine Tauschfunktion gibt es auch schon: std::swap

    Und eine Sortierfunktion gibts auch schon 🙄 Mal dran gedacht, dass man wissen sollte, wie swap funktioniert, und das Ganze ne Lehrveranstaltung ist?

    0
  • ?

    Ich möchte an der Stelle anmerken, dass es sich bei std::swap und std::sort nicht um Funktionen, sondern um Funktionsvorlagen handelt. Deren Existenz ist es ja, die es erst nützlich macht, Iteratoren als Konzepte statt als konkrete Typen zu definieren.

    @Sorex: Die Idee hinter Iteratoren ist etwas nebulös, solange man Templates (d.h. Vorlagen) noch nicht kennt. Es handelt sich bei ihnen, wie oben angemerkt, um Konzepte, was hier bedeutet, dass jeder konkrete Typ als Iterator gilt, der bestimmte Benutzungsformen erlaubt. Dabei gibt es verschiedene, ineinander geschachtelte Iteratorkonzepte. Beispielsweise ist alles ein ForwardIterator, was neben Konstruktion, Zuweisung und Vergleich mit == und != Folgendes erlaubt:

    // Sei fwditer ein ForwardIterator

*fwditer;
++fwditer;
fwditer++;
fwditer->member_des_zieltyps;

    Ein BidirectionalIterator ist etwas, was zusätzlich

    // Sei bditer ein BidirectionalIterator

--bditer;
bditer--;

    erlaubt. Jeder BidirectionalIterator ist gleichzeitig ein ForwardIterator. In ähnlicher Weise ist ein RandomAccessIterator ein BidirectionalIterator, der zusätzlich die Operationen

    // Seien raiter und raiter2 RandomAccessIteratoren

raiter += n;
raiter -= n;
raiter + n;
raiter - n;
raiter[n];

raiter - raiter2; // Entfernung voneinander
raiter <  raiter2;
raiter <= raiter2;
raiter >  raiter2;
raiter >= raiter2;

    erlaubt. Zeiger sind dementsprechend RandomAccessIteratoren (!).

    Iteratoren werden generell als Positionsangaben benutzt. Wenn v ein std::vector<int> ist, ist v.begin() die Position des ersten Elements des Vektors und v.end() die Position direkt hinter seinem letzten. Zwei Iteratoren in den selben Container können einen Bereich beschreiben; so ist es bei vielen Standardalgorithmen der Fall. Beispielsweise bedeutet

    std::vector<int> v;

...

std::sort(v.begin(), v.end());

    soviel wie "sortiere alles zwischen v.begin() und v.end()". Man kann auch

    std::sort(v.begin() + 1, v.end() - 1);

    schreiben, was soviel bedeutet wie "sortiere alles zwischen v.begin() + 1 und v.end() - 1", also alle Elemente des Vektors außer dem ersten und letzten.

    Dass das unabhängig davon möglich ist, welcher konkrete (RandomAccess)Iteratortyp benutzt wird (also dass es sowohl mit std::vector<int>::iterator als auch mit std::list<double>::reverse_iterator als auch mit int* usw. geht), liegt daran, dass es sich bei std::sort nicht um eine Funktion handelt, die einen konkreten Iteratortyp erwartet, sondern um eine Funktionsvorlage, aus der für jeden konkreten Iteratortyp, mit dem du sie benutzt, eine Funktion erstellt wird. Das ist aber ein sehr weitläufiges Thema, das ich nicht in ein paar Minuten erklären kann.

    0
  • ?

    seldon schrieb:

    Die Idee hinter Iteratoren ist etwas nebulös, solange man Templates (d.h. Vorlagen) noch nicht kennt.

    Eigentlich hat das Konzept hinter Iteratoren nichts mit Templates zu tun.

    0
  • ?

    ISO/IEC 14882:2003 24.1 (1) schrieb:

    Iterators are a generalization of pointers that allow a C++ program to work with different data structures (containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, the library formalizes not just the interfaces but also the semantics and complexity assumptions of iterators.

    0
  • ?

    Nun, dass die STL reichlich davon gebrauch macht ist schon klar, aber das Konzept oder die Idee dahinter hat nichts mit Templates, sogar nicht einmal etwas mit C++ zu tun. Iteratoren sind ein allgemeineres Konzept. Wikipedia hilft dir da sicher weiter.

    0
Anmelden zum Antworten