Immer noch Bubblesort oder schon was anderes?

[koli.bri]

Hallo.

Ich sitze gerade an einem Monatsbericht über Bublesort. Nichts großes, aber ich brauche Themen
Jetzt hab ich, um ganz sicherzugehen, mal bei Wikipedia nachgeschaut und festgestellt, dass die Beispiele dort anders sind als jenes, was ich für mich Privat benutzt habe...

Hier das Wikipedia-Beispiel: (Mal in PHP, ist für mich am geläufigsten, aber spiel ja im Grunde keine Rolle, zudem wird die Syntax da schön eingefärbt ^^)

function bubblesort($array) 
{
  $anzahl = count($array);
  for($i = 0; $i < $anzahl - 1; $i++) 
  {
    for($j = 0; $j <= $anzahl - $i - 2; $j++) 
    {
      if($array[$j] > $array[$j+1]) 
      {
        $a = $array[$j];
        $array[$j] = $array[$j+1];
        $array[$j+1] = $a;
      }
    }
  }
  return $array;
}

Und mein Beispiel:

function bubblesort($array)
{
  $anzahl = count($array);
  for($i = 0; $i < $anzahl; $i++)
  {
    for($j = 0; $j < $i; $j++)
    {
      if($array[$j] > $array[$i])
      {
        $a = $array[$j];
        $array[$j] = $array[$j+1];
        $array[$j+1] = $a;
      }
    }
  }
}

Die Unterschiede im Detail:
Ich hab in der äußeren Schleife das " - 1 " nicht drin. Gut, der letzte Schleifendurchlauf, den kann man vernachlässigen. Um den Bericht so einfach wie nur möglich zu gestalten hab ich das mal weggelassen.

Dann, die innere Schleife läuft so lange durch, bis $i gleich $j ist.

Und die Abfrage vergleicht nicht die nebenstehenden Elemente, sondern jeweils die Elemente an den Positionen der Zählschleifen.

Dennoch funktioniert mein Beispiel (Habs wegen mangelndem PHP eben nur in JavaScript nochmal testen können).

Meine Frage jetzt:
Ist mein Beispiel noch wirklich Bubblesort, oder eine andersnamige Variante?

mfg
Lukas

 

[ujs83]

Die Implementierungen bei Wikipedia unterscheiden sich teilweise deutlich voneinander ...

 

[below]

Hallo.

Ich sitze gerade an einem Monatsbericht über Bublesort.

Wo schreibt man denn Monatsberichte über Bubblesort?

Alex
EDIT: Ja, ist beides Bubblesort

 

[koli.bri]

Wo schreibt man denn Monatsberichte über Bubblesort?

Alex
EDIT: Ja, ist beides Bubblesort

In einer Bank, wenn man 6 Berichte in zwei Tagen nachmachen muss, und einem die Themen ausgehen ^^
Nicht originell, aber ich hoffe, mein Hammerbericht über Handbücher erlaubt mir diesen Patzer

 

[falkgottschalk]

Bubblesort ist ja nun bekanntlich der langsamste Sortier-Algorithmus.
Das "-1" bei der Wikipedia-Version ist schon berechtigt.
Bubblesort vergleicht bekanntlich die Elemente miteinander und schiebt das kleinste nach vorne. Die Anzahl der Vergleiche ist halt Anzahl Elemente - 1, weil bei z.B. nur 2 Elementen im Array nur 1x verglichen werden muss.

 

[foxus]

Bubblesort ist ja nun bekanntlich der langsamste Sortier-Algorithmus.

Naja, das kann man aber so nicht stehen lassen. Wenn du Grund zur Annahme hast, dass die Liste bereits vorsortiert ist und du nur prüfen willst, ob sie tatsächlich noch geordnet ist, dann ist BubbleSort verdammt schnell (da dann im Bestcase mit O "sortiert" werden kann... QuickSort schafft auch im Bestcase "nur" O(n log n)).