PHP Bubblesort Schleifenverkürzung

[Doenes91]

Hallo zusammen,


ich muss in PHP einen Bubblesort- Algorithmus programmieren. Soweit ist das kein Problem, doch wir sollen eine Schleifenverkürzung einbauen. Das heißt die Anzahl der Schleifendurchläufe der inneren Schleife soll mit jedem Durchgang um eins sinken, damit Zahlen die bereits an der richtigen Stelle stehen nicht mehr verglichen werden.
Aber ich komme einfach nicht darauf, wie ich das machen könnte! Hab scheinbar irgendwie eine Blockade im Kopf, denn so schwer kann das ja nicht sein...

Mein Bubblesort:



for($j=0; $j<$anz; $j++) {
for($k=0; $k<$anz; $k++) {


if($zahlen[$k] > $zahlen[$k+1]) {

$hilf=$zahlen[$k+1];
$zahlen[$k+1]=$zahlen[$k];
$zahlen[$k]= $hilf;
$count ++;


}


}

}

Wäre sehr nett wenn mir jemand zeigen könnte, wie ich vorgehen muss!
Danke

/edit: 10000 Rechtschreibfehler entfernt

 

[Testfall]

for($j=0; $j<$anz; $j++) {
for($k=j; $k<$anz; $k++) {


if($zahlen[$k] > $zahlen[$k+1]) {

$hilf=$zahlen[$k+1];
$zahlen[$k+1]=$zahlen[$k];
$zahlen[$k]= $hilf;
$count ++;


}


}

}

Wär's doch, oder?

 

[Madman1209]

Hi,

$laufvar = 0;
for($j=0; $j<$anz; $j++) 
{
   for($k=0; $k<$anz-$laufvar; $k++) 
   {
      if($zahlen[$k] > $zahlen[$k+1]) 
     {
        $hilf=$zahlen[$k+1];
        $zahlen[$k+1]=$zahlen[$k];
        $zahlen[$k]= $hilf;
        $count ++;
     }
   }
   $laufvar++;
}

Was hältst du davon? Hast du das so gemeint?

@Testfall

Wird die Schleifenvariable in PHP gleich zu beginn inkrementell erhöht? Falls ja: Sehr elegant Ich dachte allerdings dass dies erst am Ende der Schleife passiert.

VG,
Mad

 

[Testfall]

Naja, der erste Code geht in der äußeren Schleife alle Einträge durch und vergleicht sie in der inneren Schleife mit allen Einträgen.
Meine Version geht in der äußeren Schleife ebenfalls alle Einträge durch, in der inneren jedoch nur alle Einträge ab der Zählvariablen der äußeren, da die vorherigen ja schon mit allen verglichen sind.

Kann gut sein, dass ich da gerade was mit Quick-Sort durcheinander gewürfelt habe ...



Edit:
Ja, habe ich scheinbar; ich weiß nach dem ersten Durchgang ja noch gar nicht, ob die Zahl wirklich an der richtigen Stelle steht - es kann ja noch 'ne "Bubble" durchziehen.
'Tschuldigung.

Edit des Edit:
Meine Version passt doch ungefähr, sagt zumindest Wiki.
Also:
Es muss irgendwie darum gehen, die "oberen" Zahlen nicht bis zum Schluss durch zu exerzieren.
Die sind schon geordnet, da die größten Bubbles schon oben sind.
Das heißt, man muss in jedem Schritt nur noch n-1 Vergleiche durchführen. Der TE ist mit seinem Code aber jedes mal bei n Vergleichen.

 

[Doenes91]

Danke!
Aber leider funktioniert beides nicht, bei Testfall's Version sortiert er nicht mehr und bei Madman's ist die Anzahl der Vertauschungen nicht wirklich tiefer als zuvor. Könnte aber auch daran liegen, dass ich Zufallszahlen verwende und sich die Zahlen dadruch immer ändern.

 

[Sobber]

for($k=0; $k<($anz-$j); $k++)

Evtl auch vorher $anz-$j in ne neue Variable schreiben, keine Ahnung ob der in der Schleifenanweisung rechnet. Ist Identisch mit der Version von Madman. Hatte das gerade uebersehen.

Wenn du dir nicht sicher bist, wie oft die innere Schleife durchlaufen wird, mach dir ne Zählvariable und gib die am Ende aus.

 

[Madman1209]

Hi,

Anzahl der Vertauschungen nicht wirklich tiefer als zuvor

Was genau heisst das denn? Versteh ich nicht ehrlich gesagt.

<?php
$anz = 5;

$laufvar = 0;

for($j=0; $j<$anz; $j++) 
{
   for($k=0; $k<($anz-$laufvar); $k++) 
   {
		echo $laufvar.' ';
   }
   $laufvar++;
}

?>

Kopier dir den Code mal in eine "test.php" und rufe ihn auf. Dann siehst du was passiert.
Zuerst 4 mal, dann drei mal, dann 2 mal, dann einmal. Ich denke, so ist das in der Aufgabenstellung gemeint.

Und anstelle der "echo"-Ausgabe machst du dann deine Anweisung mit der Prüfung und dem Dreiertausch.


VG,
Mad

 

[Testfall]

Buhja, jetzt hatte ich schon nen halben Roman geschrieben und merke, andere waren schneller. Joa, hab mich in der Richtung geirrt.
Erste Schleife i von 0 bis n.
Innere Schleife von 0 bis n-i.
Dann passt das.

 

[SoDaTierchen]

Bei Bubblesort sortierst du immer zwei Paare von links nach rechts durch. Das heißt, dass nach dem Schleifendurchlauf das größte Element immer am Ende steht (es wird ja nach hinten durchgereicht). Das brauchst du also nicht mehr betrachten.

Also lass mich mal Code probieren (bin php nicht fit, also keine garantie, dass keine syntax-fehler drin sind)


for($j=0; $j<$anz; $j++) {
for($k=0; $k<$anz-j; $k++) {
if($zahlen[$k] > $zahlen[$k+1]) {
$hilf=$zahlen[$k+1];
$zahlen[$k+1]=$zahlen[$k];
$zahlen[$k]= $hilf;
$count ++;
}
}
}

Ansonsten noch was Prinzipielles: Wenn du 0-basierte Listen hast und immer k mit k+1 vergleichst: wäre es nicht sinnvoll, ein Element weniger zu durchlaufen? (Sonst kommt am Ende nen Index-Fehler) Oder macht das bei php nichts?
Und das $count brauchst du gar nicht für das Bubblesort

Noch eine Idee: Wenn du vor jeder inneren Schleife eine Variable "sorted" vom Typ bool auf True setzt, und bei jedem Tauschen auf False, könntest du die Schleife vorzeitig beenden. Wenn nämlich deine Liste sortiert ist (also du nichts mehr tauschen musstest), dann wird nach der inneren Schleife immernoch True in "Sorted" stehen und du kannst da schon abbrechen. Aber das ist so ein kleines Sahnehäubchen

 

[Doenes91]

ich habe ja eine $count innerhalb der If-Anweisung. Jedes mal wenn zwei Elemente getauscht werden, wird diese um eins erhöht. Dadurch möchte ich am Ende sehen können, wie oft getauscht wurde. Und diese Zahl wird nicht merklich beeinflusst, das meinte ich!

 

[Madman1209]

Hi,

wie willst du das auch beeinflussen, das hängt doch von den Zahlen ab die sortiert werden sollen??? Das KANNST du nicht beeinflussen, wie oft in die zweite Schleife gegangen wird sollst du beeinflussen, da macht es auch sinn weil das größte Element eh schon am Ende steht.

VG,
Mad

 

[SoDaTierchen]

Mad hat recht, die Anzahl der Vertauschungen kannst du nicht beeinflussen. Du kannst nur die Anzahl der Schleifenaufrufe reduzieren, und genau das wird auch die Aufgabe sein (Nicht jeder Schleifenaufruf ist ein Tausch!)

 

[Doenes91]

Ah, jetzt steige ich auch dahinter! Ich vermutete dass es Ziel ist die Anzahl der Vertauschungen zu verändern...vielen Dank für die Hilfe!



obwohl, eine Frage hätte ich doch noch: Ich soll ausgeben lassen, wie lange es genauert hat bis alles sortiert ist, weiß jemand wie das geht?

 

[SoDaTierchen]

Ne, gerade nicht^^ Ziel ist es, die Anzahl der Schleifenaufrufe zu verringern. Die Vertauschungen kannst du ja nicht beeinflussen, Bubblesort ist eindeutig definiert und wird, wenn richtig implementiert, immer die gleichen Anzahl Vertauschungen ausführen.

Hier was gemeint ist:

if($zahlen[$k] > $zahlen[$k+1]) {
$hilf=$zahlen[$k+1];
$zahlen[$k+1]=$zahlen[$k];
$zahlen[$k]= $hilf;
$count ++; ----Zählt die Anzahl der Vertauschungen
}

if($zahlen[$k] > $zahlen[$k+1]) {
$hilf=$zahlen[$k+1];
$zahlen[$k+1]=$zahlen[$k];
$zahlen[$k]= $hilf;
}
$count ++; -----Zählt die Anzahl der Schleifendurchläufe

Edith sagt: Nur optik verbessert, inhaltlich alles gleich geblieben

 

[Doenes91]

Danke!

Die Aufgabenstellung sieht so aus:
Wie Tauschmerker geht, auch keine Ahnung, 3 Ergebnisse bei Google...

Schreiben Sie ein PHP-Skript "bubblesort_tmsvk.php" das...
eine eingegebene Anzahl von Zufallszahlen im Bereich von 1 bis 100 erzeugt.
die erzeugten Zufallszahlen in einem Array zahlen[] ablegt.
das Array zahlen[] als html-Tabelle ausgibt.
das Array zahlen[] mittels Bubblesort-Algorithmus mit Tauschmerker und Schleifenverkürzung entsprechend einer eingegebenen Sortierrichtung sortiert.
das sortierte Array wiederum als html-Tabelle ausgibt.
die insgesamt benötigt Sortier-Zeit ausgibt.

 

[SoDaTierchen]

Tauschmerker ist leider kein offizieller Begriff, aber es gibt eigentlich nur 2 mögliche Interpretationen:
1) Es ist eine Variable, die zählt, wie oft getauscht wurde,
2) (wahrscheinlicher!) Es ist eine vorzeitige Abbruchbedingung. Wie ich schonmal oben beschrieben habe, würdest du also eine Bool-Variable einbauen, die dir prüft, ob getauscht wurde, oder nicht. wenn nicht, dann bricht die schleife ab.

Das ganze könnte (vor Berichtigung der Syntax) so aussehen:

(vorher tausch auf true setzen)
for($j=0; $j<$anz && tausch = true; $j++) {
for($k=0; $k<$anz-$j; $k++) {
$tausch = false;
if($zahlen[$k] > $zahlen[$k+1]) {
$hilf=$zahlen[$k+1];
$zahlen[$k+1]=$zahlen[$k];
$zahlen[$k]= $hilf;
$count ++;
$tausch = true;
}
}
}

Wie gesagt, ich bin in php-Syntax leider überhaupt nicht versiert, aber ich hoffe, die Idee dahinter wird klar.
Bei den anderen Aufgaben kann ich dir dann aber nicht helfen, dafür fehlt mir einfach die Syntax. Aber es gibt ja noch andere Leute hier^^ Und ganz ahnungslos bist du ja sicher auch nicht