Bubblesort Java

Om du någonsin har hört talas om sorteringsmetoder inom programmering, var det troligen bubbelsorteringsalgoritmen. Det är en berömd sådan. Varje programmerare känner till bubblesortering (eller åtminstone hört talas om det under inlärning) inte för att det är den bästa sorteringsalgoritmen i världen, utan den enklaste. Denna algoritm används vanligtvis i inlärningssyfte eller så kan du få den som en uppgift i din Java Junior Intervju. Java Bubble sorteringsalgoritm är mycket lätt att förstå, men det är inte en effektiv sådan. Hur som helst, låt oss ta reda på det.

Vad är sortering

Först och främst måste du förstå vad sortering är i allmänhet och vad vi kan sortera i Java-program. Om vi ​​kan jämföra två eller flera element eller objekt efter något av deras attribut, betyder det att de kan sorteras efter detta attribut. Till exempel siffror i stigande eller fallande ordning eller ord i alfabetisk ordning. Därför måste elementen vara jämförbara med varandra. Förresten, delarna av vad? I Java kan vi jämföra elementen i samlingar. Till exempel kan vi sortera Array eller ArrayList av heltal, Strings och så vidare.

Hur fungerar bubblesortering

Låt oss säga att vi behöver sortera en matris med heltal i stigande ordning, det vill säga från det minsta till det största numret. Först går vi längs hela arrayen och jämför vartannat närliggande element. Om de är i fel ordning (vänster granne är större än den högra) byter vi dem. Vid första passet i slutet kommer det att visas det största elementet (om vi sorterar i stigande ordning). Man kan säga att det största elementet "doppar upp". Det är anledningen till Bubble-sortalgoritmens namn. Vi upprepar det första steget från det första till det näst sista elementet. Vi har det näst största elementet på näst sista plats. Och så vidare. Vi kan förbättra en algoritm lite genom att checka ut om minst ett utbyte i föregående steg gjordes. Om det inte är det, slutar vi springa längs arrayen.

Exempel på bubbelsortering

Låt oss sortera arrayen av heltal, den som du kan se nedan på en bild. Steg 1: vi går igenom arrayen. Algoritmen börjar med de två första elementen (med index 0 och 1), 8 och 7, och kontrollerar om de är i rätt ordning. Självklart, 8 > 7, så vi byter dem. Därefter tittar vi på de andra och tredje elementen (index 1 och 2), nu är dessa 8 och 1. Av samma skäl byter vi dem. För tredje gången jämför vi 8 och 2 och åtminstone 8 och 5. Vi gjorde fyra byten totalt: (8, 7), (8, 1), (8, 2) och (8, 5). Ett värde på 8, det största i denna array, dök upp i slutet av listan till rätt position. Resultatet av att det första steget i Bubblesorteringsalgoritmen fungerar är nästa array: Steg 2. Gör samma sak med (7,1), (7,2) och (7,5). 7 är nu på näst sista plats, och vi behöver inte jämföra den med "svansen" på listan, den är redan sorterad. Resultatet av att det andra steget av Bubblesorteringsalgoritmen fungerar är nästa array: Som du kanske ser är denna array redan sorterad. Hur som helst bör Bubble Sort-algoritmen komma igång åtminstone en gång till. Steg 3. Vi går igenom arrayen en gång till. Inget att byta här, så om vi använder "förbättrad" Bubblesorteringsalgoritm (med att kolla om minst ett utbyte i föregående steg gjordes) är detta steg det sista.

Bubblesort Java-kod

Bubblesort Java-förverkligande

Låt oss skapa två metoder för Bubblesortering. Den första, bubbleSort(int[] myArray) är en plan. Det går genom arrayen varje gång. Den andra, optimizedBubbleSort(int myArray[]) optimeras genom att stoppa algoritmen om den inre slingan inte orsakade något byte. Räknaren visar hur många steg du gjorde när du sorterade. Här har vi Bubblesort Java-förverkligande:

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 Bubblesort Java-algoritmarbete:

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]

Hur effektivt är bubbelsortering?

Bubblesortering är en av de enklaste algoritmerna att implementera men den är inte effektiv. Det kräver ett par kapslade slingor. Även i en optimerad version av algoritmen i värsta fall (varje element i datamängden är i omvänd ordning till den önskade) itererar den yttre slingan en gång för vart och ett av de n elementen i datamängden . Den inre slingan itererar n gånger för första gången, ( n-1 ) för andra, och så vidare. För att få alla n , element sorterade, måste looparna exekveras n*(n-1)/2 gånger. Den kallar O(n ² )tidskomplexitet och innebär att algoritmen gör cirka 500 000 jämförelser för 1000 element i en array. Bubbelsorteringsalgoritmen är dock ganska effektiv vid minnesanvändning (minneskomplexiteten är O(n) ) och är riktigt bra för nästan sorterade små datamängder.