Boblesort Java

Hvis du noen gang har hørt om sorteringsmetoder i programmering, var det mest sannsynlig boblesorteringsalgoritmen. Det er en berømt en. Hver programmerer kjenner til boblesortering (eller i det minste hørt om det mens han lærte), ikke fordi det er den beste sorteringsalgoritmen i verden, men den enkleste. Denne algoritmen brukes vanligvis til læringsformål, eller du kan få den som en oppgave i ditt Java Junior Intervju. Java Bubble-sorteringsalgoritmen er veldig enkel å forstå, men den er ikke effektiv. Uansett, la oss finne ut av det.

Hva er sortering

Først av alt må du forstå hva sortering er generelt og hva vi kan sortere i Java-programmer. Hvis vi kan sammenligne to eller flere elementer eller objekter etter noen av deres attributter, betyr det at de kan sorteres etter denne attributten. For eksempel tall i stigende eller synkende rekkefølge eller ord alfabetisk. Derfor må elementene være sammenlignbare med hverandre. Forresten, elementene i hva? I Java kan vi sammenligne elementene i samlinger. For eksempel kan vi sortere Array eller ArrayList av heltall, strenger og så videre.

Hvordan fungerer boblesortering

La oss si at vi må sortere en rekke heltall i stigende rekkefølge, det vil si fra det minste til det største tallet. Først går vi langs hele matrisen og sammenligner hvert 2 naboelement. Hvis de er i feil rekkefølge (venstre nabo er større enn den høyre), bytter vi dem. Ved første pass på slutten vil det dukke opp det største elementet (hvis vi sorterer i stigende rekkefølge). Du kan si at det største elementet "dukker opp". Det er grunnen til Bubble-sortalgoritmenavnet. Vi gjentar det første trinnet fra det første til det nest siste elementet. Vi har det nest største elementet på nest siste plass. Og så videre. Vi kan forbedre en algoritme litt ved å sjekke ut om minst én utveksling i forrige trinn ble gjort. Hvis det ikke er det, slutter vi å løpe langs matrisen.

Eksempel på boblesortering

La oss sortere utvalget av heltall, det ene du kanskje ser nedenfor på et bilde. Trinn 1: vi går gjennom matrisen. Algoritmen starter med de to første elementene (med indeksene 0 og 1), 8 og 7, og sjekker om de er i riktig rekkefølge. Åpenbart 8 > 7, så vi bytter dem. Deretter ser vi på det andre og tredje elementet (indeks 1 og 2), nå er disse 8 og 1. Av samme grunner bytter vi dem. For tredje gang sammenligner vi 8 og 2 og minst 8 og 5. Vi gjorde fire utvekslinger totalt: (8, 7), (8, 1), (8, 2) og (8, 5). En verdi på 8, den største i denne matrisen, dukket opp på slutten av listen til riktig posisjon. Resultatet av det første trinnet i boblesorteringsalgoritmen som fungerer, er den neste matrisen: Trinn 2. Gjør det samme med (7,1), (7,2) og (7,5). 7 er nå i nest siste plassering, og vi trenger ikke sammenligne den med "halen" på listen, den er allerede sortert. Resultatet av det andre trinnet i boblesorteringsalgoritmen er neste array: Som du kanskje ser, er denne arrayen allerede sortert. Uansett bør Bubble Sort-algoritmen komme i gang minst én gang til. Trinn 3. Vi går gjennom matrisen en gang til. Ingenting å bytte her, så hvis vi bruker "forbedret" Bubble Sort algoritme (med å sjekke ut om minst én utveksling på forrige trinn ble gjort) er dette trinnet det siste.

Java-kode for boblesortering

Java-realisering med boblesortering

La oss lage to metoder for boblesortering. Den første, bubbleSort(int[] myArray) er en plan. Den går gjennom arrayet hver gang. Den andre, optimizedBubbleSort(int myArray[]) er optimalisert ved å stoppe algoritmen hvis indre sløyfe ikke forårsaket noe bytte. Telleren viser deg hvor mange trinn du gjorde mens du sorterte. Her har vi boblesort Java-realisering:

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 av boblesorterings Java-algoritmearbeid:

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 av de enkleste algoritmene å implementere, men den er ikke effektiv. Det krever et par nestede løkker. Selv i en optimalisert versjon av algoritmen i verste fall (hvert element i datasettet er i omvendt rekkefølge til det ønskede) itererer den ytre sløyfen én gang for hvert av de n elementene i datasettet. Den indre løkken itererer n ganger for første gang, ( n-1 ) for andre, og så videre. Derfor, for å få alle n , elementer sortert, må løkkene utføres n*(n-1)/2 ganger. Den kaller O(n ² )tidskompleksitet og betyr at algoritmen gjør omtrent 500 000 sammenligninger for 1000 elementer i en matrise. Imidlertid er boblesorteringsalgoritme ganske effektiv i minnebruk (minnekompleksitet er O(n) ) og er veldig bra for nesten sorterte små datasett.