Diskussion:Bubblesort

Variante mit Abbruchbedingung

Dieser Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind. Hierzu sind in der Regel mehrere Durchläufe erforderlich.

Die "dumme" Variante von BubbleSort durchläuft das Feld auch dann weiter, wenn eigentlich keine Durchläufe mehr erforderlich sind, weil das Feld schon sortiert ist. Die verbesserte Variante mit Abbruchbedingung wird erst im Abschnitt "Varianten" angesprochen. --Head 11:34, 1. Sep 2003 (CEST)

Laufzeit, Vorteile

Interessante Fehler, obwohl es doch in der En-Version richtig steht. Laufzeit bei der Standard Version ist immer O(n^2). Damit gibt es auch nur noch einen Vorteil, nämlich In-place-Verfahren.

Beispiele

Macht es wirklich Sinn, hier 16 Beispiele in verschiedenen Programmiersprachen anzugeben? Ich würde denken, das widerspricht dem Sinn einer Enzyklopädie. M.E. sollte hier nur der Pseudocode (und ganz evtl. noch ein Beispiel (die Sprache könnt ihr euch aussuchen)) stehen. MfG Michael K 16:18, 9. Jan. 2007 (CET)

Java-Beispiel

Das Java-Beispiel benutzt ein im Konstruktor limitiertes Feld, aber viel schlimmer ist, dass der Sortieralgorithmus eine spezialisierte Abbruchbedigung hat, die auch noch sehr wie ein Hack aussieht. Zu einem Beispielzwecke sollte allerdings mein Beispiel wohl eher genügen (auch wenn es nicht den Anspruch an eine Wiederverwendbare Klasse hat).

public class Sort {

  private static int Liste []={1,2,3,4,6,6,6,66666,66,3,1};

  public static void main(String[] a)
  {
    int temp;
    boolean sortiert=true;
    int len=Liste.length;
    while(sortiert)
    {
      sortiert=false;
      for(int i=1;i<len;i++)
      {
        if(Liste[i]<Liste[i-1])
        {
          temp=Liste[i];
          Liste[i]=Liste[i-1];
          Liste[i-1]=temp;
          sortiert=true;
        }
      }
    }
    //Zwecks Ausgabe
    //for(int i=0;i<Liste.length;i++)
    //System.out.println(Liste[i]+",");
  }

} --EX10DeaDth 14:46, 10. Feb 2006 (CET)

Igitt... sowas packt man doch nicht einfach in die Main-Methode...

--62.46.210.169 00:32, 26. Mai 2006 (CEST)

Kann es sein das das Beispiel wo man nur sieht was gemacht wird leicht falsch ist? ich glaube es fehlen da ein paar Zeilen!!

Ist hier nicht die x-Achsenbeschriftung mit der y-Achsenbeschriftung vertauscht? Die großen Werte Wandern von links nach rechts???

Varianten

Ist Cocktailsort nun schneller, oder nicht? Und wenn ja, dann warum? Ist ein wenig seltsam formuliert :)

nicht besser, dennoch schneller?

die Stelle widerspricht sich selbst.

Nein, widerspricht sich nicht, da steht das kleine Wörtchen kann davor. Bubblesort dauert immer gleich lang, es sei denn, wir haben eine Abbruchbedingung. Beim Shakersort KANN durch die in beide Richtungen verlaufende Sortierung der Vorgang schneller erfolgen, weil nicht so viel Vertauschungen nötig sind - siehe Extremfall absteigende Sortierung -> aufsteigende Sortierung, bei der die Sortierung schon nach n/2 Durchläufen erledigt ist. 13:57, 19. Feb. 2007 (CET) Odysseus1904 14:01, 19. Feb. 2007 (CET) ------

Implementation Pascal/Delphi

Die Variablenbezeichnung (AArray) ist nicht besonders gelungen und erschwert das Verständnis. Außerdem handelt es sich hier schon um eine der Varianten und nicht um reines Bubblesort (das nicht überprüft, ob das Feld vielleicht schon eher fertig sortiert ist) Deswegen hier mein Vorschlag für eine simple Pascal-Implementation (weiß nicht ob ich es gleich auf der Hauptseite ändern soll):

 const SIZE = 20000;
 type TFeld = array[1..SIZE] of integer;
 
 procedure bubblesort(var f:TFeld);
 var i,j,temp:integer;
 begin
     for i:=SIZE downto 2 do begin
         for j:=2 to i do begin
             if f[j-1] > f[j] then begin
                 temp := f[j-1];
                 f[j-1] := f[j];
                 f[j] := temp;
             end;
         end;
     end;
 end;

Antwort: Der Variablenname war wirklich Grütze, änder es ruhig. Ich würde noch die zwei überflüssigen begin/end Streichen, Merke: überflüssiger Formalismus verwirrt mehr, als dass er nützt. igel+- 18:26, 25. Jul 2006 (CEST)

Ich frage mich persönlich, wie man der "dummen" Bubblesort-Variante den Vortritt vor der "intelligenten" Version geben kann, schließlich soll man bei wikipedia doch mehr mitnehmen, als nur die reinen Fakten. "AArray" war an sich auch nicht schlecht gewählt, sondern einfach nur angliziert, wie die gesamte PASCAL-Sprache ("array" = "Feld").

c#

Wäre es nicht sinnvoll auch ein Beispiel für C# mit einzufügen? (unsigniert)

Ich hab grad das folgende Zitat aus dem Artikel entfernt. Zum einen handelt es sich nicht um einen Bubblesort, weil keine Prüfung stattfindet, zum anderen wird der Artikel m.E. durch die Implementierungen überfrachtet. --Lexikorn 20:17, 3. Aug. 2009 (CEST)

"und in C# implediert

   public class sort
   {
       public int[] a={12,45,4,9,6,7,4654,44564,455,74,85,49,78,1}; //Die Zahlenfolge
       public void bubblesort()
       {
           int t;
           int i;
           int j;
           for (j = 1; j < a.Length; j++)
           {
               for (i = 0; i < a.Length - 1; i++)
               {
                   if (a[i] > a[i + 1])
                   {
                       t = a[i];
                       a[i] = a[i + 1];
                       a[i + 1] = t;
                   }
                }
           }
       }
   }" (aus dem Artikel hierher übernommen. Autor: 91.66.98.201.)

fuer massenhaft expliziten code haben wir ja mittlerweile ein buch auf wikibooks; ist auf der artikelseite verlinkt. -- seth 23:10, 4. Aug. 2009 (CEST)

Perl

Ich bin mir ziemlich sicher, dass die Perl-Implementierung kein Bubblesort sondern eher ein verkappter Selectionsort ist. Denn es wird in der inneren Schleife immer das i-te mit dem j-ten Element verglichen und nicht zwei benachbarte Elemente, also das j-te mit dem (j+/-1)-ten. Andere Meinungen?

Nachdem ich scheinbar nicht der Einzige bin, der den bisher angegeben Algorithmus fuer nen Selectionsort haelt, hab ich mal eine korrigierte Fassung erstellt. Leider konnte ich sie nicht direkt in den Artikel einpflegen :-(. Aber hier ist meine leicht modifizierte Version:

sub bubblesort {
    for my $i (0 .. $#_) {
        for my $j (1 .. ($#_ - $i)) {
            if ($_[$j] < $_[$j-1]) {
                ($_[$j-1], $_[$j]) = ($_[$j], $_[$j-1]);
            }
        }
    }
}

Was soll die Sperrung

Warum ist die Seite gesperrt. Ich finde ein Link auf das Programm Animierte Algorithmen fehlt( Wieso funzt das speichern mit links unter Firefox nicht mehr ? ) --217.184.239.173 16:21, 14. Jan. 2007 (CET)

Viel zu viele Implementierungen

Der Artikel enthätl viel zu viele Implementierungen! Man hat den Eindruck, der Artikel würde nur noch daraus bestehen und das bisschen Text ist nur schmuckes Beiwerk. Irgendwie geht das doch vollkommen am Sinn und Zweck der Wikipedia vorbei oder nicht? Ich denke, es wäre weitaus sinnvoller EINE Implementierung in Pseudocode zu machen. Das macht den ganzen Artikel um einiges übersichtlicher. Jeder, der Programmiererfahrung hat, wird mit Pseudocode etwas anfangen und diesen dann in "seine" Sprache übersetzen können. -- LordHorst - Moin 18:59, 28. Feb. 2007 (CET)

Verdirb uns nicht den Spaß! igel+- 16:33, 9. Jan. 2007 (CET)

Sorry, aber dafür gibt's die uncyclopedia (oder wie das Ding heißt). Meinetwegen zwei Beispielimplementierungen, wenn's denn unbedingt sein muss, den Rest kann man getrost nach Wikibooks oder so verschieben. --Complex ^обс. 19:16, 28. Feb. 2007 (CET)

Also, welche nehmen wir denn raus? --Complex ^обс. 01:40, 13. Mär. 2007 (CET)

Du machst es also wahr, hm? Naja, hättest du wohl die Güte, die jetzige Liste vorher auf Wikibooks zu transferieren und von diesem Artikel aus dahinzuverlinken? Ich denke, man sollte den Algorithmus in einer Hochsprache (sagen wir: deutsch) und in einer Maschinensprache (Assembler) darstellen. Als Assemblersprache würde mir MMIXAL gut gefallen. Falls unbedingt auch eine praxisnahe Programmiersprache nötig ist oder gewünscht wird (ich denke, das ist keinesfalls nötig, wenn man das aber anders sieht:) wäre ich für Algol, weils so schön alt ist und Beweisverfahren einfacher zugänglich als eine objektorientierte Sprache. igel+- 02:25, 13. Mär. 2007 (CET)

Ich waere dafuer, wenn wir die Programmbeispiele herausnehmen, dass wir nur Pseudocode stehen lassen. Wir koennen die Programmierbeispiele auch auf eine Unterseite kopieren und diese vom Text aus verlinken. Cheers, --Pedro.Gonnet 09:27, 13. Mär. 2007 (CET)

Spannender ist doch, wohin wir die Implementierungen schieben. Zum Löschen sind sie viel zu schade. igel+- 00:13, 14. Mär. 2007 (CET)

Wie waers mit einer Unterseite Bubblesort/Programmbeispiele? --Pedro.Gonnet 09:16, 14. Mär. 2007 (CET)

Also, ich habe einmal Benutzer:ThePacker um Rat gebeten. Je nachdem was er sagt verwurste ich es entweder zum Wikibook oder zur Wikipedia-Liste, habe ich beschlossen. igel+- 14:56, 14. Mär. 2007 (CET)

ThePacker sagt, er hat in Wikibooks für so etwas bestenfalls im http://de.wikibooks.org/wiki/Wikibooks:Abstellraum Platz. Na gut, also als Wikipedia-Liste. igel+- 23:12, 19. Mär. 2007 (CET) (edited -- ThePacker 23:35, 19. Mär. 2007 (CET)) Quasi als Grundlage für die Programmierbücher. -- ThePacker 23:35, 19. Mär. 2007 (CET)

Im Pseudocode ist wohl noch ein kleiner Fehler. n ist ja die Länge des Array - 1. Wenn die Indizes des Array von 0 bis Länge ( A ) - 1 laufen, dann ist n der Index des letzten Elementes. Weil die Schleife aber von 0 bis n läuft, wird beim letzten Durchlauf A[ i ] > A[ i + 1 ] also A[ n ] > A[ n + 1 ] abgefragt. Das Element A[ n + 1 ] gibt es aber gar nicht! Es müsste doch heissen:

für jedes i in 0 bis n - 1 wiederhole:

Ich dachte, ich frage erst mal nach, bevor ich den Code einfach abändere. --129.132.9.72 19:21, 17. Apr. 2007 (CEST)

Was man (ich) noch tun könnte

Der durchschnittliche Sortieraufwand sollte berechnet werden (bei angenommener Gleichverteilung der Größen der zu sortierenden Elemente auf ... tja, auf was? auf {1,...,n} vielleicht. igel+- 00:13, 14. Mär. 2007 (CET)

Meinst Du einfache average-case-Analyse, wie hier? --Complex ^обс. 00:18, 14. Mär. 2007 (CET)

ja, genau ... igel+- 00:42, 14. Mär. 2007 (CET)

Pseudocode

Habe eben schon eine kleine Änderung vorgenommen, da ich den Pseudocode wirklich vollkommen verwirrend fand mit "falls ende"... Da dürfte man auch sehr gerne for oder if zu sagen.. (nicht signierter Beitrag von 129.132.211.17 (Diskussion | Beiträge) 10:30, 13. Aug. 2009 (CEST))

Im Pseudocode ist deutsche Sprache durchaus OK. Aber gut, dass du die Verwirrung beseitigt hast, da bin ich ganz deiner Meinung. --Lexikorn 15:01, 13. Aug. 2009 (CEST)

Parallelisierter bubblesort

Hallo, gerade habe ich auf der Erstsemestereinführung der Informatik-Fachschaft meiner Uni eine Art "Human Bubblesort" beobachten können. Dabei werden Menschen nach irgendwelchen Eigenschaften sortiert. Der Algorithmus unterscheidet sich vom normalen Bubblesort dadurch, dass die Vergleiche und Vertauschungen parallel stattfinden können (jeder Mensch hat quasi einen eigenen Thread), und dadurch das ganze natürlich schneller geht. Hier eine formalisierte (getaktete) Variante:

parallelsort(Mensch[1..n] menschen):
  int takt = 0;
  wiederhole:
    takt += 1
    vertauscht = false
    Für alle i ∈ { 1 ... n-1 } : 
      falls gerade(i + takt):
         falls (menschen[i+1] < menschen[i]):
            vertausche(menschen[i], menschen[i+1])
            vertauscht = true
  solange vertauscht;

Hierbei wird die "Für alle"-Schleife jeweils parallel ausgeführt. Wenn ich das richtig sehe, braucht der Algorithmus im Worst Case (und wohl auch im Average Case) O(n) Schritte (d.h. Durchläufe der äußeren Schleife), im Best Case O(1). Für einen normalen Computer ist das natürlich nicht sinnvoll (weil der keine n Prozessoren hat, für interessante n). (Unter en:Odd-even sort ist dieser Algorithmus aufgeführt, ohne die "parallel"-Bedingung.) In der menschlichen Variante geschieht das natürlich ohne Takt, und jeder vergleicht sich selbst nach einem Tausch nach rechts mit seinem (neuen) rechten Nachbar, nach einem Tausch nach links mit seinem neuen linken Nachbar (sofern der nicht gerade beschäftigt ist), wodurch das alles etwas chaotischer wird. Da wir hier aber keine Forschung treiben sollen, kennt jemand dazu Quellen, bevor ich dazu etwas in den Artikel schreibe? -- Paul E. 10:52, 12. Okt. 2010 (CEST)

Ja, eine Quelle dafür ist Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 222 (englisch). 

--Gms 21:09, 20. Feb. 2012 (CET)

Hasen und Schildkröten — rly?

Ist Turtles and Rabbits wirklich ein üblicher Begriff um die entsprechenden Elemente zu kategorisieren? Liest sich ja etwas albern. Ich befürchte, dass die einzige Verwendung (neben den Wikipedia-Artikeln) und die Quelle davon dieser Byte Magazine Artikel von 1991 ist. — Der Abschnitt über schnell bzw. langsam 'wandernde' Elemente ist ja sinnvoll im WP-Artikel - aber vielleicht sollte man ihn überarbeiten um die Hasen/Schildkröten-Analogie zu vermeiden ...

--Gms 00:33, 22. Feb. 2012 (CET)

Laufzeitverhalten auf modernen Rechnern

Ich habe soeben den einfachen Bubble-Sort (ohne besondere Abbruchbedingung bei bereits sortiertem Array) in Java programmiert und in einer Testreihe zu meinem Erstaunen festgestellt, dass das umgekehrte Array nur etwa 10% mehr Sortierzeit als das sortierte Array und das zufällig besetzte Array mehr als 4-mal soviel benötigt. Nach erfolgloser Fehlersuche kann ich mir das nur so erklären, dass hier automatische Techniken zur Sprung- und Sprungzielvorhersage (Intel Core-i7) zum Tragen kommen. Muss man sowas bei Laufzeitberechnungen zukünftig mit einkalkulieren? Ist jedenfalls blöd für den Informatik-Unterricht, wenn Theorie und Praxis so offensichtlich auseinanderlaufen. --188.101.235.178 22:57, 17. Apr. 2013 (CEST)

Sehr seltsam, aber weißt Du denn, was Deine Java-VM so im Hintergrund macht? Da hast Du z.B. einen Just-In-Time-Compiler und evtl. auch Profiler, die von Lauf zu Lauf optimieren etz. Ich würde dafür eine vernünftig vor der laufzeit compilierte Sprache (C/C++, Pascal, oder Java mit 'nem richtigen Compiler, also ohne Bytecode!!!) verwenden, bei Allem Anderen gibt's Seiteneffekte, die man nicht kennt und nur schwer fassen kann. --Jkrieger (Diskussion) 23:25, 17. Apr. 2013 (CEST)

Rekursive Implementierung

ich weiss ich weiss: "noch eine Implementierung!?" Ich fand die Aufgabenstellung interessant, also hier in rekursiv.

public List<Integer> sort(List<Integer> numbers) { bubbleSort(numbers, 0, 1); return numbers; }

private void bubbleSort(List<Integer> numbers, Integer position, Integer runs) { if (position < numbers.size() - runs) {

// pick two Integer a = numbers.get(position); Integer b = numbers.get(position + 1);

// place back numbers.set(position, a >= b ? b : a); numbers.set(position + 1, a >= b ? a : b);

// next step position++; } else { // start over position = 0; runs++; } if (runs < numbers.size()) bubbleSort(numbers, position, runs); } (nicht signierter Beitrag von 208.49.239.230 (Diskussion) 21:40, 25. Jun. 2013 (CEST))

In der Praxis wird Bubblesort kaum eingesetzt, da andere Verfahren ein besseres Laufzeitverhalten haben.

Diesen Satz halte ich für sehr fraglich. Komplexere Sortierverfahren lohnen sich erst ab einer bestimmten Schwelle, beispielsweie 100 oder 1000. Es gibt daher eine Menge Anwendungen bei denen Bubblesort das geeignete Mittel ist, beispielsweise Sortieren von Tabellen auf Webseiten, Radiosender im Autoradio, Lesezeichen im Browser ... Die Aussage bezieht sich vermutlich auf vorgefertigte Software-Packages wie sort (Unix). --Siehe-auch-Löscher (Diskussion) 06:29, 24. Nov. 2015 (CET)

Geschichte?

Ein kurzer Absatz über die Historie des Algorithmus wäre interessant. Seit wann ist er bekannt, wer hat ihn erfunden, wo wurde er zuerst erwähnt... (nicht signierter Beitrag von Titule (Diskussion | Beiträge) 22:39, 22. Jun. 2019 (CEST))

Gruß vom C64

Folgenden Code habe ich hiermit in der Schreibweise des C64 zur Verfügung gestellt. Ich denke dass es so besser verständlich ist. In diesem Fall wird der Algorithmus mit "GOSUB 1010" als Unterprogramm gestartet.

N = Anzahl der zu sortierenden Zahlen

A(...) = Das Array

1000 REM **** BUBBLE-SORT ****
1010 IF N<2 THEN RETURN
1020 FOR I=1 TO N-1
1030 IF A(I)>A(I+1) THEN GOTO 1060
1040 NEXT I
1050 RETURN
1060 FOR IB=I TO N-1
1070 IF A(IB)<=A(IB+1) THEN GOTO 1110
1080 C=A(IB)
1090 A(IB)=A(IB+1)
1100 A(IB+1)=C
1110 NEXT IB
1120 GOTO 1020

--77.21.163.85 02:55, 25. Nov. 2020 (CET)

"Hasen und Schildkröten" - Fehler behoben

Ich habe mir erlaubt einen Fehler zu beheben. Im Artikel stand als Beispiel, dass bei 99 zu sortierenden Werten L=0 / R=99 gesetzt werden muss. Diese falsche Aussage hat mich heute sehr viel Nerven gekostet, weil ich nicht verstanden habe, warum meine Übersetzung nach Visual Basic immer dann nicht funktioniert hat, wenn sich hinter den zu sortierenden Werten, eine Null im Array befindet. Bei 99 Werten muss R=98 lauten. --77.21.163.85 23:33, 30. Mai 2021 (CEST)