Boble sortering Java

Hvis du nogensinde har hørt om sorteringsmetoder i programmering, var det højst sandsynligt boblesorteringsalgoritmen. Det er en berømt. Enhver programmør kender til boblesortering (eller i det mindste hørt om det, mens de lærte), ikke fordi det er den bedste sorteringsalgoritme i verden, men den nemmeste. Denne algoritme bruges normalt til læringsformål, eller du kan få den som en opgave i dit Java Junior-interview. Java Bubble-sorteringsalgoritme er meget let at forstå, men den er ikke effektiv. Anyway, lad os finde ud af det.

Hvad er sortering

Først og fremmest skal du forstå, hvad sortering generelt er, og hvad vi kan sortere i Java-programmer. Hvis vi kan sammenligne to eller flere elementer eller objekter efter nogen af ​​deres attributter, betyder det, at de kan sorteres efter denne attribut. For eksempel tal i stigende eller faldende rækkefølge eller ord alfabetisk. Derfor skal elementerne være sammenlignelige med hinanden. Forresten, elementerne i hvad? I Java kan vi sammenligne elementerne i samlinger. For eksempel kan vi sortere Array eller ArrayList af heltal, Strings og så videre.

Hvordan fungerer boblesortering

Lad os sige, at vi skal sortere en række heltal i stigende rækkefølge, det vil sige fra det mindste til det største tal. Først går vi langs hele arrayet og sammenligner hver 2 naboelementer. Hvis de er i den forkerte rækkefølge (venstre nabo er større end den højre), bytter vi dem. Ved det første gennemløb i slutningen vises det største element (hvis vi sorterer i stigende rækkefølge). Du kan sige, det største element "dukker op". Det er grunden til Bubble-sortalgoritmens navn. Vi gentager det første trin fra det første til det næstsidste element. Vi har det næststørste element på den næstsidste plads. Og så videre. Vi kan forbedre en algoritme en lille smule ved at tjekke ud, hvis der blev foretaget mindst én udveksling i det foregående trin. Hvis det ikke er, stopper vi vores løb langs rækken.

Eksempel på boblesortering

Lad os sortere rækken af ​​heltal, det ene, du måske kan se nedenfor på et billede. Trin 1: vi gennemgår arrayet. Algoritmen starter med de to første elementer (med indeks 0 og 1), 8 og 7 og tjekker, om de er i den rigtige rækkefølge. Det er klart, 8 > 7, så vi bytter dem. Dernæst ser vi på andet og tredje element (indeks 1 og 2), nu er disse 8 og 1. Af samme årsager bytter vi dem. For tredje gang sammenligner vi 8 og 2 og mindst 8 og 5. Vi lavede fire udvekslinger i alt: (8, 7), (8, 1), (8, 2) og (8, 5). En værdi på 8, den største i dette array, dukkede op i slutningen af ​​listen til den korrekte position. Resultatet af det første trin i boblesorteringsalgoritmen er det næste array: Trin 2. Gør det samme med (7,1), (7,2) og (7,5). 7 er nu i næstsidste position, og vi behøver ikke sammenligne den med listens "hale", den er allerede sorteret. Resultatet af det andet trin af boblesorteringsalgoritmen er det næste array: Som du måske kan se, er dette array allerede sorteret. Alligevel burde Bubble Sort-algoritmen komme i gang mindst én gang til. Trin 3. Vi gennemgår arrayet endnu en gang. Der er ikke noget at bytte her, så hvis vi bruger "forbedret" Bubble Sort algoritme (med at tjekke ud, om der blev foretaget mindst én udveksling på det forrige trin), er dette trin det sidste.

Bubblesort Java-kode

Bubblesort Java realisering

Lad os oprette to metoder til boblesortering. Den første, bubbleSort(int[] myArray) er en plan. Den løber gennem arrayet hver gang. Den anden, optimizedBubbleSort(int myArray[]) er optimeret ved at stoppe algoritmen, hvis den indre løkke ikke forårsagede nogen swap. Tælleren viser dig, hvor mange trin du gjorde, mens du sorterede. Her har vi Bubble sort Java realisation:

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)));
   }
}

Resultatet af boblesorterings Java-algoritmearbejde:

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]

Hvor effektiv er boblesortering?

Boblesortering er en af ​​de nemmeste algoritmer at implementere, men den er ikke effektiv. Det kræver et par indlejrede løkker. Selv i en optimeret version af algoritmen i værste fald (hvert element i datasættet er i omvendt rækkefølge af det ønskede) itererer den ydre sløjfe én gang for hvert af de n elementer i datasættet. Den indre sløjfe gentager n gange for første gang, ( n-1 ) for anden, og så videre. Derfor, for at få alle n , elementer sorteret, skal løkkerne udføres n*(n-1)/2 gange. Det kalder O(n ² )tidskompleksitet og betyder, at algoritmen udfører omkring 500.000 sammenligninger for 1000 elementer i et array. Boblesorteringsalgoritmen er dog ret effektiv i hukommelsesbrug (hukommelseskompleksitet er O(n) ) og er virkelig god til næsten sorterede små datasæt.