Problem mit Bubblesort
-
In meinem Buch ist folgendes Beispiel, allerdings fehlt in der markierten
zeile etwas und ich weiß nicht was./* Bubble sort */ #include <string.h> #include <stdio.h> #include <stdlib.h> void bubble (char *items, int count); int main (void) { char s[255]; puts ("Enter a String:"); gets (s); bubble (s,strlen(s)); printf ("The sorted String is: %s.\n",s); gets (s); return 0; } void bubble (char *items, int count) { register int a,b; register char t; for (a = 1; a < count; a++) { for (b = count -1; b = a; b--) { if (items[b-1] items[b]){ // was muss dazwischen stehen? t = items[b-1]; items[b-1] = items[b]; items[b] = t; } } } }Wenn mir jemand erklären könnte was genau diese doppellte Schleife tut, wäre
ich auch sehr dankbar, kann es irgendwie nicht ganz nachvollziehen.
-
Habe eben ein wenig weitergelesen und beim Shaker-Sort fehlt an den Stellen auch
irgendwie etwas, habe sie wieder markiert und hoffe ihr könnt mir helfen
/* Der Shaker Sort */ void shaker (char *items, int count) { register int a; int exchange; char t; do { exchange = 0; for (a = count -1; a /* hier fehlt etwas */ 0; a--) { if (items[a-1] /*hier auch*/ items[a]) { t = items[a-1]; items[a-1] = items[a]; items[a] = t; exchange = 1; } } for (a = 1; a < count; a++) { if (items[a-1] /* hier */ items[a]) { t = items[a-1]; items[a-1] = items[a]; items[a] = t; exchange = 1; } } } while (exchange); /* so lange sortieren wie keine Austauschvorgänge stattfinden */ }
-
Ohne Garantie müsste da ein > hin
for (a = 1; a < count; a++) { for (b = count -1; b = a; b--) { if (items[b-1] > items[b]){ // das ganze soll ja vertauscht werden wenn items[b-1] größer ist als items[b] t = items[b-1]; items[b-1] = items[b]; items[b] = t; } } }
-
do { exchange = 0; for (a = count -1; a > 0; a--) { // Solange bis a = 1 ist, dadurch wird alles durchlaufen if (items[a-1] > items[a]) { // selbe wie beim Bubblesort, wenn items[a-1] größer ist, tauschen t = items[a-1]; items[a-1] = items[a]; items[a] = t; exchange = 1; } } for (a = 1; a < count; a++) { if (items[a-1] > items[a]) { // das selbe Prozedere wie oben t = items[a-1]; items[a-1] = items[a]; items[a] = t; exchange = 1; } } } while (exchange); Alles ohne Gewähr, müsste aber so stimmen ^^
-
Ok, dann macht das auch sinn
kannst du mir den shake-sort mal erklären, er funktioniert zwar und ein
printf direkt nach jeder for-schleife mit dem String, half mir auch nicht zu
verstehen wie das gehen soll.Die For-Schleife geht doch jedesmal den gesamten
String durch und das 2mal aber trotzdem wird nur 1Zeichen pro Schleife getauscht.Edit:
Irgendetwas an dem Bubblesort stimmt nicht, das erzeugt 100% CPU-Auslastung und
läuft bei 6Zeichen noch nach 25Sekunden, scheint irgenwie eine Endlosschleife zu
sein, kann das sein?
-
Galeon schrieb:
Ohne Garantie müsste da ein > hin
for (a = 1; a < count; a++) { for (b = count -1; b = a; b--) { if (items[b-1] > items[b]){ // das ganze soll ja vertauscht werden wenn items[b-1] größer ist als items[b] t = items[b-1]; items[b-1] = items[b]; items[b] = t; } } }In der zweiten For-Schleife steht ja als Vergleich "b = a", dies steht auch so
im Buch kann dies für die Endlosschleife zuständig sein?
Irgendwie macht das nämlich auch kein sinn, aber wüsst jetzt nicht was dort
hingehört, würde vllt. mal != sagen aber sicher bin ich mir nicht.Edit:
Es muss tatsächlich ungleich heißen, dann funktioniert es auch
-
oh f*** meinte ungleich, sry ^^, soll ja solange laufen wie b ungleich a ist ^^.
-
Ich denke mal das beschreibt das ganz gut :).
"Sortieren durch Austauschen - Shakersort
Der Shakersort stellt eine geringfügige Verbesserung des Bubblesorts dar: Um weit von der richtigen Stelle liegende Elemente schneller einzusortieren, wird nach jedem Durchlauf die Laufrichtung umgekehrt. Die ``schüttelnde'' Bewegung des Verfahrens hat dem Algorithmus wohl seinen Namen verliehen... "
-
So nen Satz hab ich unter dem beispiel auch stehen, verstehe aber den Zweck
der beiden for-schleifen nicht, die durchlaufen ja beide den string komplett
und das nacheinander.
Somit ist nach der ersten der String eigentlich schon sortiert, aber wie ich
durch die Hilfs-Printfs feststellen muss, arbeitet das Programm sowie es eigentlich
soll, aber ich vertsehe nicht wie das möglich sit
-
Habe mit dem Sortieren durch Einfügen auch ein Problem, der funktioniert nicht,
kam mir beim abtippen schon komisch vor.
Aber was ich da ändern muss dass es geht hab ich noch nicht rausgefunden.
Hoffe jemand von euch kann mir helfen/* Sortieren durch einfügen */ #include <string.h> #include <stdio.h> #include <stdlib.h> void insert (char *items, int count); int main (void) { char s[255]; puts ("Enter a String:"); gets (s); insert (s,strlen(s)); printf ("The sorted String is: %s.\n",s); gets (s); return 0; } void insert (char *items, int count) { register int a,b; char t; for (a = 1; a < count; a++) { t = items[a]; for (b = a-1; (b = 0) && (t < items[b]); b--) items[b+1] = items[b]; items[b+1] = t; } }Komm mir irgendwie langsam doof vor, aber der QuickSort geht auch nicht, hat
irgendetwas das nen Stack Underflow hervorruft:/* Quicksort */ #include <string.h> #include <stdio.h> #include <stdlib.h> void q_start ( char *items, int count); void qs (char *items, int left, int right); int main (void) { char s[255]; puts ("Enter a String:"); gets (s); q_start (s,strlen(s)); printf ("The sorted String is: %s.\n",s); gets (s); return 0; } void q_start (char *items, int count) { qs (items, 0, count-1); } void qs (char *items, int left, int right) { register int i,j; char x,y; i = left; j = right; x = items[(left+right)/2]; do { while ((items[i] < x) && (i << right)) i++; while ((x < items[j]) && (j > left)) j--; if (i < j) { y = items[i]; items[i] = items[j]; items[j] = y; i++;j--; } }while ( i < j); if (left < j) qs (items, left, j); if (i < right) qs (items, i, right); }
-
Kann mir denn keiner weiterhelfen? Oder Beispiele dieser Algorithmen liefern
die auch funktionieren? Sind bisher die einzigsten Beispiele in diesem Buch
die nicht funktionieren.
-
http://www.ralph.timmermann.org/software/sortieren.htm
Dort sind verschiedenste Sortieralgorithmen gut erklärt.zum Insertion-Sort:
In der zweiten Schleife muss es b>0 heissen und nicht b=0.zum Quicksort:
void qs (char *items, int left, int right) { register int i,j; char x,y; i = left; j = right; x = items[(left+right)/2]; do { while (items[i] < x) i++; while (x < items[j]) j--; if (i < j) { y = items[i]; items[i] = items[j]; items[j] = y; } if (i<=j) i++;j--; }while ( i < j); if (left < j) qs (items, left, j); if (i < right) qs (items, i, right); }Die Überprüfung, von i<right und j>left ist unnötig, da i nie grösser werden kann als (left+right)/2. Umgekehrt kann j nie kleiner werden als (left+right)/2. Der Grund liegt darin, dass Du ja das Element, das an dieser Position steht mit i bzw. j vergleichst. Wenn i=(left+right)/2 ist, läuft die while-Schleife nicht mehr weiter, weil ihre Bedingung nicht mehr erfüllt ist. Dasselbe gilt für j.
Die Erhöhung/Erniedrigung von i/j habe ich aus der Bedingung zum Vertauschen ausgegliedert, weil diese Operationen auch vorgenommen werden müssen, wenn i==j ist.
Der Quicksort-Algorithmus ist übrigens der einzige Algorithmus, den Du hier zeigst, dessen Laufzeit besser ist als n*n (d.h. die Laufzeit steigt quadratisch zur Anzahl Elemente, die sortiert werden sollen...), nämlich im Mittel nur n*log(n) (im schlechtesten Fall zwar auch n*n, aber der tritt nur ein, wenn Du versuchst eine bereits sortierte Liste zu sortieren
). Darum solltest Du, wenn immer möglich diesen Algorithmus (oder einen mit ähnlich gutem Laufzeitverhalten) verwenden. Die Algorithmen mit n*n Laufzeit sind bei grossen Listen nicht mehr brauchbar, weil sie ewig brauchen um fertig zu sortieren...Gruss,
Andreas
-
ok,danke
Der Insert-Sort funktioniert auch so nicht:
Enter a String:
asdbfhl
The sorted String is: lssssss.Werde mir die Seite einmal anschauen