Bubblesort


Einfacher Bubblesort

Ein einfacher Bubblesort ist im folgenden Quelltext dargestellt. Dieser Bubblesortalgorithmus läuft allerdings ohne zusätzliche Abbruchbedingung und es werden in jedem Durchgang stets alle Elemente durchlaufen (sehr lange Laufzeit).

 

Bubblesort vergleicht jeweils immer 2 Elemente des Arrays(Liste) miteinander,beruhend auf deren Größe. Ist das Element A > Element B werden deren Plätze innerhalb des Arrays getauscht, falls Element A < Element B wird nichts getauscht. Der Algorithmus durchläuft bei einem Durchlauf immer das gesammte Array und beansprucht dabei viel Zeit.

A     B     C     D     E

10     8     6     2     4

 

1.

B <  A     C     D     E    

8     10     6     2     4

 

2.

B     C <  A     D     E

8     6     10     2     4

 

3.

B     C     D  <  A      E

8     6     2      10     4

und so weiter

Am Ende sieht die Sortierung so aus

D     E     C     B     A

2     4     6     8     10

 

Dies wäre der Code wie man ihn in Java eingeben kann, wenn es ein zugehöriges Array gibt:

int j = 0;

while(j < zahlenfeld.length){

     for(int i = 0;i < zahlenfeld.length - 1;i++){

          if(zahlenfeld[i] > zahlenfeld[i+1]){

               int temp = zahlenfeld[i+1];

               zahlenfeld[i+1] = zahlenfeld[i];

               zahlenfeld[i] = temp;

          }

     }

     j++;

}

 

 

Optimierter Bubblesort

Der optimierte Bubblesort-Algorithmus bricht ab, wenn in einem Durchlauf nicht mehr getauscht worden ist, denn auch in den nächsten Durchgängen wird dann nicht mehr getauscht und es kann bereits zu einem früheren Zeitpunkt abgebrochen werden.

Außerdem läuft der optimierte Bubblesort-Algorithmus nicht mehr durch das gesamte Feld, sondern lässt die im i-ten Durchlauf bereits sortierten i Elemente im hinteren Arraybereich unbeachtet. Mit jedem Durchlauf wird der sortierte Bereich um 1 größer.

 

 

Dies wäre der Code wie man ihn in Java eingeben kann, wenn es ein zugehöriges Array gibt:

 

for (int i = 0; i < zahlenfeld.length && getauscht == true; i++) {

            getauscht = false;

            for (int y = 0; y < zahlenfeld.length-1; y++) {

                if(zahlenfeld[y] > zahlenfeld[y + 1]) {

                    größer= zahlenfeld[y];

                    kleiner= zahlenfeld[y + 1];

                    zahlenfeld[y] = kleiner;

                    zahlenfeld[y + 1] = größer;  

                    getauscht = true;

                }

            }

        }