PHP Bubblesort ohne For- und If-Schleifen?

...komplette Frage anzeigen Bild 1 - Mein Versuch - (Computer, PC, programmieren) Bild 2 - Normal - (Computer, PC, programmieren)

2 Antworten

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

Korrektur: 

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

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

0

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

0
@Appleistbesser

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.  

0

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

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ß

0
@Appleistbesser

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

0

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

0

Was möchtest Du wissen?