Immer noch Bubblesort oder schon was anderes?

Dieses Thema im Forum "Mac OS X Entwickler, Programmierer" wurde erstellt von koli.bri, 22.11.2006.

  1. koli.bri

    koli.bri Thread Starter Gast

    Hallo.

    Ich sitze gerade an einem Monatsbericht über Bublesort. Nichts großes, aber ich brauche Themen :D
    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 ^^)

    PHP:
    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:

    PHP:
    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
     
  2. ujs83

    ujs83 MacUser Mitglied

    Beiträge:
    56
    Zustimmungen:
    0
    MacUser seit:
    19.01.2005
    Die Implementierungen bei Wikipedia unterscheiden sich teilweise deutlich voneinander ...
     
  3. below

    below MacUser Mitglied

    Beiträge:
    13.882
    Zustimmungen:
    1.086
    MacUser seit:
    15.03.2004
    Wo schreibt man denn Monatsberichte über Bubblesort?

    Alex
    EDIT: Ja, ist beides Bubblesort
     
  4. koli.bri

    koli.bri Thread Starter Gast

    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 :D
     
  5. falkgottschalk

    falkgottschalk MacUser Mitglied

    Beiträge:
    24.026
    Zustimmungen:
    1.598
    MacUser seit:
    22.08.2005
    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.
     
  6. foxus

    foxus MacUser Mitglied

    Beiträge:
    37
    Zustimmungen:
    0
    MacUser seit:
    13.01.2006

    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(n) "sortiert" werden kann... QuickSort schafft auch im Bestcase "nur" O(n log n)).
     
Die Seite wird geladen...

Diese Seite empfehlen