Entwickler-Ecke
Programmiersprachen (Server) - [php]BubbleSort-Problem
Marco D. - Fr 05.10.07 23:10
Titel: [php]BubbleSort-Problem
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| do {
$swapped = false;
for ($i = 0 ; $i <= Count($relevant_results) ; $i++) {
if ($relevant_results[$i]->ranking_value < $relevant_results[$i+1]->ranking_value) {
$temp = $relevant_results[$i];
$relevant_results[$i] = $relevant_results[$i+1];
$relevant_results[$i+1] = $temp;
$swapped = true;
}
}
} while ($swapped == false); |
Ich verwende zur Sortierung der Suchergebnisse nach Relevanz (Wert ist in ranking_value gespeichert; liegt zwischen 0 und 1) BubbleSort. Die größte Relevanz soll oben stehen. Funktioniert soweit, dass die größte Relevanz an zweiter und die zweitgrößte Relevanz an erster Stelle steht. Wie muss ich den Algorithmus abändern, damit es funktioniert?
Heiko - Sa 06.10.07 10:19
Hallo,
das ist nur von ganz paar Fehlern ;).
Ich hoffe, hier ist jetzte kein Fehler drin:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| $cnt = Count($relevant_results);
for ($i = 0; $i<$cnt-1; $i++){
for ($j = $i; $j<$cnt-1; $i++){
if ($relevant_results[$i]->ranking_value > $relevant_results[$i+1]->ranking_value){
$tmp = $relevant_results[$i];
$relevant_results[$i] = $relevant_results[$i+1];
$relevant_results[$i+1] = $tmp;
}
}
} |
Das müsste so stimmen, ist aber ungetestet ;).
PHP bietet aber schon nen ganz paar fertige Befehle (bisher nicht genutzt, aber mir bekannt ;) ). Such einfach mal nach "sort" bei php.net. Dort findest du auch gleich die verschiedensten Fehler für php.
r2c2 - Sa 06.10.07 10:51
Den Code kann man noch optimieren, auch, wenn das der originale BubbleSort ist. Sowas wie Break(wenn bemerkt wird, dass alles schon sortiert ist) gibts in PHP doch auch, oder? Hab schon ne ganze Zeit lang kein PHP mehr gemacht. Langsam fangen die Kenntnisse an zu rosten...
 Heiko hat folgendes geschrieben: |
PHP bietet aber schon nen ganz paar fertige Befehle (bisher nicht genutzt, aber mir bekannt ;) ). Such einfach mal nach "sort" bei php.net. Dort findest du auch gleich die verschiedensten Fehler für php. |
Die hab ich ganz vergessen, jo. Ich hab die schon benutzt. Funktionieren gut. Wie weiß ich aber nicht mehr auswendig ==> kann man aber ja alles nachgucken...
Ansosnten bleibt noch zu erwähnen, dass BubbleSort nicht unbedingt der beste Algorithmus ist. Nimm lieber MinSort, InsertionSort oder QuickSort(je nach Fall):
MinSort: Einfach
InsertioonSort: Sehr gut, bei teilw. Vorsortierung
QuickSort, schnell aber rekursiv und instabil
mfg
Christian
Marco D. - Sa 06.10.07 13:39
Ich könnte jetzt Heikos Code kopieren und einfügen. Jedoch wäre das für mich nicht zufriedenstellend.
Meinen Original-Code (ganz oben) habe ich nach folgendem Pseudocode entworfen:
http://de.wikipedia.org/wiki/Bubblesort#Formaler_Algorithmus
Warum klappt das so nicht? D.h., was unterscheidet meinen PHP- von diesem Pseudo-Code bezüglich der Funktionsweise?
Heiko - So 07.10.07 10:07
Du hast das "n" in dem Code nicht beachtet ;)
GTA-Place - So 07.10.07 10:16
Und es heißt solange vertauscht, spricht while ($swapped). IMHO müssen es eh drei Gleichheitszeichen sein, wenn du === false/true schreibst.
Heiko - So 07.10.07 10:21
| GTA-Place hat folgendes geschrieben: |
| Und es heißt solange vertauscht, spricht while ($swapped). |
Ne, dass ist ne repeat-until-Schlöeife dort, also eine do-while-Schleife, so wie er es schon hat. Er hat lediglich vergessen n zu verwenden (das kann man nicht rauskürzen) ;). Und Count-1 müsste es heißen ;).
| GTA-Place hat folgendes geschrieben: |
| IMHO müssen es eh drei Gleichheitszeichen sein, wenn du === false/true schreibst. |
Ne, zwei reichen. Eine Typenüberprüfung ist hier nicht erforderlich, denn man sieht, dass nur true oder false drin sein kann. Man nutzt ===, wenn eine Funktion false, true, Strings und Zahlen gemischt ausgeben kann, ansonsten lässt man es weg ;).
Marco D. - So 07.10.07 15:04
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| do {
$n = Count($relevant_results) - 1;
$swapped = false;
for ($i = 0 ; $i < $n ; $i++) {
if ($relevant_results[$i]->ranking_value < $relevant_results[$i+1]->ranking_value) {
$temp = $relevant_results[$i];
$relevant_results[$i] = $relevant_results[$i+1];
$relevant_results[$i+1] = $temp;
$swapped = true;
}
}
$n--;
} while ($swapped); |
So funzt es jetzt, vielen Dank Leute. :P
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!