3. Sortieralgorithmus BubbleSort

Sortieralgorithmus BubbleSort

  • S

    Hallo allerseits.

    Wir haben gestern an der FH Sortieralgorithmen durchgenommen und ich hab mir mal zum Testen den BubbleSort aus dem Skript kopiert.
    Den gibt's in 2 Versionen - ein mal mit Pointer, einmal ohne.

    Die letztere Version funktioniert tadellos, die erste leider nicht, bin aber anscheinend nicht in der Lage herauszufinden weshalb.

    int main() 
{
    vector<int> field;

	srand((unsigned)time(0));

	for (int i=0; i<10; i++)
	{
		 field.push_back(rand()%(20+1));
		 cout << " " << field[i] << " ";  //Ausgabe unsortiert
	}

	cout << "\n";

	bubbleSort(&field[0], &field[field.size()-1]);
    //Warum funktioniert an dieser Stelle folgender Aufruf nicht?..
    //bubbleSort(&field.begin(), &field.end()) -> Compiler meckert

	for (int i=0; i<10; i++)
	{
		 cout << " " << field[i] << " ";  //Ausgabe sortiert
	}

    return 0;
}

    void bubbleSort(int* pf, int* pl )
{
  //pf = pfirst --  pl = plast

     for( int* pi=pl-1;  pi>pf; --pi )
     {
          for( int *pj=pf ;  pj<pi ;  ++pj )
          {
               if( *(pj+1) < *pi )
                   mySwap( *pj, *(pi+1) );
          }
     }
}

//--------------------SWAP---------------------

void mySwap( int& a, int& b ) 
{
     int help = a;
     a = b; b = help;
}

    Falls von Interesse, hier noch die ohne-Pointer-Version

    void bubbleSort( int a[],  int first, int last )
{
     for( int i=last-1;  i>first; --i )
     {
        for( int j=first ;  j<i ;  ++j )
        {
            if( a[ j+1 ] < a[ j ] )
                mySwap( a[ j ], a[ j+1 ] );
        }
     }

//--------Aufruf in main()--------------------------
//---->bubbleSort(&field[0], 0, (field.size()-1)+1);
}

    MfG

    0
  • E

    Du meine Güte! Wer hat den Code geschrieben?

    0
  • S

    EOutOfResources schrieb:

    Du meine Güte! Wer hat den Code geschrieben?

    Wenn du den BubbleSort meinst -> unser Prof, ziemlich fähiger Mann, auch wenn er manchmal etwas.. kompliziert wird 😃

    Die main() ist nur ein lala-Code zum Testen.

    0
  • C

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

    Erstens ist "Compiler meckert" eine sehr präzise Fehlerbeschreibung. Und zweitens liefern begin() und end() Iteratoren in deinen vector<>, das ist eine Verallgemeinerung von Pointern - und davon die Adresse zu bilden ist weder sinnvoll noch notwendig (wenn es überhaupt erlaubt ist).

    PS: Wenn du schon mit STL-Containern arbeitest, dann bau deine Funktionen auch so, daß sie Iteratoren darauf entgegennehmen.

    0
  • E

    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

    0
  • S

    [quote="CStoll"]

    PS: Wenn du schon mit STL-Containern arbeitest, dann bau deine Funktionen auch so, daß sie Iteratoren darauf entgegennehmen.

    Wie gesagt, ist nicht meine Funktion, sondern aus dem Skript.

    Kriege diese Fehlermeldung, wenn ich's so mache wie gefragt:

    'bubbleSort': Konvertierung des Parameters 1 von 'std::_Vector_iterator<_Myvec> *' in 'int *' nicht möglich
1>          with
1>          [
1>              _Myvec=std::_Vector_val<int,std::allocator<int>>
1>          ]
1>          Die Typen, auf die verwiesen wird, sind nicht verknüpft; die Konvertierung erfordert einen reinterpret_cast-Operator 
oder eine Typumwandlung im C- oder Funktionsformat.
    0
  • 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
Anmelden zum Antworten