[php]BubbleSort-Problem

Marco D. · Verfasst: Fr 05.10.07 23:10

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

//Sortierung der Suchergebnisse nach Relevanz (höchste Relevanz ganz oben)
        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?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

r2c2 · Beiträge: 324 Erhaltene Danke: 2 Linux

Hallo

so wie ich das sehe, stimmt die Schleifenbedingung nicht. Du brichst sofort ab, wenn du einmal getauscht hast...

BubbleSort implementiert man aslo anders. Siehe:
de.wikipedia.org/wiki/Bubblesort
www.sortieralgorithm...ubblesort/index.html
r2c2.weingut-rehn.de/facharbeit.htm

mfg

Christian

_________________
Kaum macht man's richtig, schon klappts!

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Hallo,

das ist nur von ganz paar Fehlern

.
Ich hoffe, hier ist jetzte kein Fehler drin:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

//Sortierung der Suchergebnisse nach Relevanz (höchste Relevanz ganz oben)
$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 · Beiträge: 324 Erhaltene Danke: 2 Linux

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

_________________
Kaum macht man's richtig, schon klappts!

Marco D. · Verfasst: 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: de.wikipedia.org/wik...Formaler_Algorithmus
Warum klappt das so nicht? D.h., was unterscheidet meinen PHP- von diesem Pseudo-Code bezüglich der Funktionsweise?

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

Heiko · Beiträge: 3169 Erhaltene Danke: 11

Du hast das "n" in dem Code nicht beachtet

GTA-Place · Verfasst: 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.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Heiko · Beiträge: 3169 Erhaltene Danke: 11

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. · Verfasst: So 07.10.07 15:04

markieren

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.

_________________
Pascal keeps your hand tied. C gives you enough rope to hang yourself. C++ gives you enough rope to shoot yourself in the foot

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme