Blasensortierung Java

Wenn Sie jemals von Sortiermethoden in der Programmierung gehört haben, war es höchstwahrscheinlich der Blasensortierungsalgorithmus. Es ist berühmt. Jeder Programmierer kennt die Blasensortierung (oder hat zumindest beim Lernen davon gehört), nicht weil es der beste Sortieralgorithmus der Welt ist, sondern weil er der einfachste ist. Dieser Algorithmus wird normalerweise zu Lernzwecken verwendet oder Sie erhalten ihn als Aufgabe in Ihrem Java Junior-Interview. Der Java-Bubble-Sortieralgorithmus ist sehr einfach zu verstehen, jedoch nicht effizient. Wie auch immer, lass es uns herausfinden.

Was ist Sortieren?

Zunächst müssen Sie verstehen, was Sortieren im Allgemeinen ist und was wir in Java-Programmen sortieren können. Wenn wir zwei oder mehr Elemente oder Objekte anhand eines ihrer Attribute vergleichen können, bedeutet dies, dass sie nach diesem Attribut sortiert werden können. Zum Beispiel Zahlen in aufsteigender oder absteigender Reihenfolge oder Wörter alphabetisch. Daher müssen die Elemente miteinander vergleichbar sein. Übrigens, die Elemente von was? In Java können wir die Elemente von Sammlungen vergleichen. Zum Beispiel können wir Array oder ArrayList von Ganzzahlen, Strings usw. sortieren.

Wie funktioniert die Blasensortierung?

Nehmen wir an, wir müssen ein Array von ganzen Zahlen in aufsteigender Reihenfolge sortieren, also von der kleinsten zur größten Zahl. Zuerst gehen wir das gesamte Array durch und vergleichen alle zwei benachbarten Elemente. Wenn sie in der falschen Reihenfolge sind (der linke Nachbar ist größer als der rechte), vertauschen wir sie. Beim ersten Durchgang erscheint am Ende das größte Element (wenn wir in aufsteigender Reihenfolge sortieren). Man könnte sagen, das größte Element „springt auf“. Das ist der Grund für den Namen des Bubble-Sortieralgorithmus. Wir wiederholen den ersten Schritt vom ersten bis zum vorletzten Element. Das zweitgrößte Element haben wir auf dem vorletzten Platz. Usw. Wir können einen Algorithmus ein wenig verbessern, indem wir prüfen, ob im vorherigen Schritt mindestens ein Austausch durchgeführt wurde. Ist dies nicht der Fall, hören wir auf, entlang des Arrays zu laufen.

Beispiel für eine Blasensortierung

Lassen Sie uns das Array von Ganzzahlen sortieren, das Sie unten auf einem Bild sehen können. Schritt 1: Wir gehen das Array durch. Der Algorithmus beginnt mit den ersten beiden Elementen (mit den Indizes 0 und 1), 8 und 7, und prüft, ob sie in der richtigen Reihenfolge sind. Offensichtlich ist 8 > 7, also tauschen wir sie aus. Als nächstes schauen wir uns das zweite und dritte Element (Indizes 1 und 2) an, nun sind das 8 und 1. Aus den gleichen Gründen vertauschen wir sie. Zum dritten Mal vergleichen wir 8 und 2 und mindestens 8 und 5. Wir haben insgesamt vier Austausche vorgenommen: (8, 7), (8, 1), (8, 2) und (8, 5). Der Wert 8, der größte in diesem Array, wurde am Ende der Liste an der richtigen Position angezeigt. Das Ergebnis des ersten Arbeitsschritts des Bubble-Sort-Algorithmus ist das nächste Array: Schritt 2. Machen Sie dasselbe mit (7,1), (7,2) und (7,5). 7 befindet sich jetzt an vorletzter Stelle und wir müssen sie nicht mit dem „Ende“ der Liste vergleichen, sie ist bereits sortiert. Das Ergebnis des zweiten Schritts des Bubble-Sort-Algorithmus ist das nächste Array: Wie Sie vielleicht sehen, ist dieses Array bereits sortiert. Auf jeden Fall sollte der Bubble-Sort-Algorithmus noch mindestens einmal in Gang kommen. Schritt 3. Wir gehen das Array noch einmal durch. Hier gibt es nichts zu tauschen. Wenn wir also den „verbesserten“ Bubble-Sort-Algorithmus verwenden (mit Prüfung, ob im vorherigen Schritt mindestens ein Austausch durchgeführt wurde), ist dieser Schritt der letzte.

Java-Code mit Blasensortierung

Blasensortierung in Java

Lassen Sie uns zwei Methoden für die Blasensortierung erstellen. Die erste, bubbleSort(int[] myArray) ist eine ebene. Es durchläuft jedes Mal das Array. Der zweite, optimierteBubbleSort(int myArray[]) wird optimiert, indem der Algorithmus angehalten wird, wenn die innere Schleife keinen Austausch verursacht hat. Der Zähler zeigt Ihnen, wie viele Schritte Sie beim Sortieren gemacht haben. Hier haben wir die Java-Realisierung von Bubble Sort:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

Das Ergebnis der Arbeit des Java-Algorithmus „Bubble Sort“:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

Wie effizient ist die Blasensortierung?

Die Blasensortierung ist einer der am einfachsten zu implementierenden Algorithmen, aber nicht effizient. Es erfordert ein Paar verschachtelter Schleifen. Selbst in einer optimierten Version des Algorithmus wird im schlimmsten Fall (jedes Element des Datensatzes liegt in umgekehrter Reihenfolge zum gewünschten vor) die äußere Schleife einmal für jedes der n Elemente des Datensatzes durchlaufen. Die innere Schleife iteriert n -mal beim ersten Mal, ( n-1 ) beim zweiten Mal und so weiter. Um also alle n Elemente zu sortieren, müssen die Schleifen n*(n-1)/2 Mal ausgeführt werden. Es nennt O(n ² )Zeitkomplexität und bedeutet, dass der Algorithmus etwa 500.000 Vergleiche für 1.000 Elemente eines Arrays durchführt. Allerdings ist der Blasensortierungsalgorithmus ziemlich effektiv bei der Speichernutzung (die Speicherkomplexität beträgt O(n) ) und eignet sich wirklich gut für fast sortierte kleine Datensätze.