Frage von Appleistbesser, 75

PHP Bubblesort ohne For- und If-Schleifen?

Hallo zusammen. Stellt euch vor: Ihr sollt ein einfaches Sortierprogramm für ein Array schreiben. Ihr bekommt das Bubblesort- Verfahren vorgestellt, jedoch bloß die Struktur, nicht den Code. Ihr fangt an und ihr schreibt so was: (siehe Bild 1). Dann bekommt ihr den normalen Code vorgestellt (For-For-If (Bild 2)). Jetzt hat euch der Ehrgeiz gepackt. Der erste Code macht in meinen Augen perfekten Sinn, nur werden nach "Submit" nur die eingegebenen Zahlen, jedoch unsortiert, oder gar nichts angezeigt, nicht einmal eine Fehlermeldung.

Erbitte Hilfe. Hier der Link zu meinen Dateien: https://www.dropbox.com/sh/iiai9xr6i7b375u/AAB4-xDwX_jrZa7KnJoVnLRTa?dl=0

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von nikolaiki, 23

Du mixt hier zwei unpassende Verfahren.
foreach ist ein leistungsfaehiges Mittel um ein Array zu durchlaufen ohne sich um Zeiger und Array grössen Gedanken machen zu müssen.
Aber woher weiß man welches der Nachfolger von $x ist?
Also holst du dir doch einen Zeiger: $j. Womit der positive Grundgedanke futsch ist.
Und weil das ganze so kompliziert geworden ist, vertust du dich auch
noch mit dem Zeiger: $j ist immer zwei Schritte voraus statt nur einen.
Blöd gelaufen. Sorry wenn ich's so hart ausdrücke, aber falsch ist falsch.

Bubble Sort macht doch folgendes:
Im ersten Durchlauf wird jedes Element mit seinem Nachfolger verglichen.
Wenn das linke groeser ist als das rechte, wird getauscht.
Das wiederholt man bis es nichts mehr zu tauschen gibt.

Jetzt gibt es 2 Optimierungen:
- Nach jedem Durchlauf steht das groesste Element rechts, dadurch ist der naechste Lauf 1 kuerzer
- Sobald es nichts mehr zu tauschen gibt kann man aufhoeren

also:
$anz=count($all);
do {
  for ($i=0; $i<($anz-1); $i++)
    if($all[i] > $all[i+1]) {tausche};
  $anz--;
} while($anz > 1);

Die erste Optimierung ist untergebracht, der Durchlauf wird jedes mal 1 kuerzer
zweite Otimierung:
$anz=count($all);
do {
  $fertig=true;
  for ($i=0; $i<($anz-1); $i++)
    if($all[i] > $all[i+1]) {tausche; $fertig=false;};
  $anz--;
} while($anz > 1 && $fertig==false);

Voila, sobald nicht mehr getauscht wurde, sind wir fertig
Kommentar von nikolaiki ,

Korrektur: 

while(($anz > 1) && ($fertig==$false));

Wegen der Operator Rangfolge bindet das && staerker als == deshalb sind hier Klammern erforderlich

Kommentar von Appleistbesser ,

Okay, danke. Dann werde ich den Code nochmal etwas umschreiben.

Kommentar von nikolaiki ,

Viel Erfolg :-) 
Den For-Schleifen auf dem zweiten Bild fehlen übrigens beide Optimierungen: Die innere Schleife wird nach jeder Runde nicht um 1 verkürzt und es wird nicht abgebrochen, wenn nach Durchlauf der Schleife keine Vertauschung erfolgt ist. Das ist aber wichtig, sonst ist es kein Bubblesort.  

Antwort
von Malemeister, 32

Hallo,

ohne deinen Code angeguckt zu haben (nur die Bilder habe ich mir angeguckt), vermute ich das du das Bubblesort Verfahren noch nicht ganz verstanden hast. Wikepedia erklärt das eigentlich ganz gut.

Wenn du aber möchtest das wir deinen Code angucken, dann poste ihn bitte über Pastebin oder sowas. Ich jedenfalls werde mir nicht irgendwelche Dateien aus einer fremden Cloud einfach so runterladen!

Grüße

Kommentar von Appleistbesser ,

Alles klar, danke und dass Sie sich nichts einfach runterladen wollen ist verständlich. Hier der Pastebin-Link: http://pastebin.com/kaasCWgF

Es geht mir hierbei weniger darum, das Bubblesort- Verfahren richtig zu schreiben, sondern eher darum, dass mein Code mir richtig erscheint, aber nicht funktioniert. Und das regt mich auf. Wäre echt super, wenn Sie mir helfen könnten.

Gruß

Kommentar von Malemeister ,

Vorweg: Du sollst ein Array sortieren. Du sollst kein Array durchlaufen und dann die Zahlen per "echo" ausgeben. Wenn die Aufgabe ist ein Array zu sortieren, dann sollte man sich daran halten. Einmal, weil es eben die Aufgabenstellung ist aber zum anderen auch (und das ist am wichtigsten) hat es schon seinen Grund warum die Aufgabe genau so gestellt wurde. Du machst nämlich hier auch den entscheidenden Denkfehler und das hängt auch mit deinem "echo" zusammen.

Nagut, lass uns einfach mal logisch überlegen: Wie funktioniert Bubblesort?

Im Grundegenommen geht Bubblesort das Array solange von vorne nach hinten durch bis die Zahlen alle in einer Reihenfolge sind. Wir brauchen hierbei also 2 Schleifen. Eine um einmal das komplette Array einmal durchzugehen. Nun brauchen wir noch eine Schleife die in der ersten Schleife das Array wieder durchgeht. In dieser Schleife werden dann auch die Zahlen geprüft und ggf. getauscht.

Das was du machst:

Du gehst mit er foreach Schleife das Array einmal komplett durch. Richtig? Ja

Schauen wir uns deine nächste Schleife an:

Wann wiederholt sich die while Schleife? Richtig, wenn das Statemant "true" ist. Wir erinnern uns an Bubblesort zurück: Bubblesort geht an dieser stelle jede Zahl des Arrays durch. Machst du das auch? Oder bricht while eventuell die Schleife ab, weil das Statemant nicht mehr "true" ist?

Ich hoffe das hilft dir als kleinen Denkanstoß.

Tipp: Wenn du schon Stundenlang davor sitzt, mach eine kurze Pause. Das hilft!

Grüße

Kommentar von Appleistbesser ,

Okay. Danke für die Mühe. Ich glaube, ich habe es begriffen.

Keine passende Antwort gefunden?

Fragen Sie die Community