Sortare cu bule Java

Dacă ați auzit vreodată de metode de sortare în programare, cel mai probabil a fost algoritmul de sortare cu bule. Este una celebră. Fiecare programator știe sortarea cu bule (sau cel puțin a auzit de el în timp ce învață) nu pentru că este cel mai bun algoritm de sortare din lume, ci cel mai ușor. Acest algoritm este folosit de obicei în scopuri de învățare sau îl puteți obține ca sarcină în interviul Java Junior. Algoritmul de sortare Java Bubble este foarte ușor de înțeles, însă nu este unul eficient. Oricum, hai să ne dăm seama.

Ce este sortarea

În primul rând, trebuie să înțelegeți ce este sortarea în general și ce putem sorta în programele Java. Dacă putem compara două sau mai multe elemente sau obiecte după oricare dintre atributele lor, înseamnă că pot fi sortate după acest atribut. De exemplu, numere în ordine crescătoare sau descrescătoare sau cuvinte în ordine alfabetică. Prin urmare, elementele trebuie să fie comparabile între ele. Apropo, elementele de ce? În Java, putem compara elementele Colecțiilor. De exemplu, putem sorta Array sau ArrayList de numere întregi, șiruri și așa mai departe.

Cum funcționează sortarea cu bule

Să presupunem că trebuie să sortăm o matrice de numere întregi în ordine crescătoare, adică de la cel mai mic la cel mai mare număr. În primul rând, mergem de-a lungul întregii matrice și comparăm fiecare 2 elemente învecinate. Dacă sunt în ordine greșită (vecinul din stânga este mai mare decât cel din dreapta), le schimbăm. La prima trecere la final va apărea cel mai mare element (dacă sortăm în ordine crescătoare). Puteți spune că cel mai mare element „apare”. Acesta este motivul numelui algoritmului de sortare cu bule. Repetăm ​​primul pas de la primul până la ultimul element. Avem al doilea cel mai mare element pe penultimul loc. Și așa mai departe. Putem îmbunătăți puțin un algoritm verificând dacă a fost făcut cel puțin un schimb la pasul anterior. Dacă nu este, ne oprim alergarea de-a lungul matricei.

Exemplu de sortare cu bule

Să sortăm șirul de numere întregi, cel pe care îl puteți vedea mai jos pe o imagine. Pasul 1: trecem prin matrice. Algoritmul începe cu primele două elemente (cu indici 0 și 1), 8 și 7 și verifică dacă sunt în ordinea corectă. Evident, 8 > 7, așa că le schimbăm. În continuare, ne uităm la al doilea și al treilea element (indicii 1 și 2), acum acestea sunt 8 și 1. Din aceleași motive, le schimbăm. Pentru a treia oară comparăm 8 și 2 și, cel puțin 8 și 5. Am făcut patru schimburi în total: (8, 7), (8, 1), (8, 2) și (8, 5). O valoare de 8, cea mai mare din această matrice, a apărut la sfârșitul listei în poziția corectă. Rezultatul primului pas de lucru al algoritmului de sortare cu bule este următorul tablou: Pasul 2. Faceți același lucru cu (7,1), (7,2) și (7,5). 7 este acum în penultima poziție și nu trebuie să-l comparăm cu „coada” listei, este deja sortat. Rezultatul celui de-al doilea pas al algoritmului de sortare cu bule este următoarea matrice: După cum puteți vedea, această matrice este deja sortată. Oricum, algoritmul Bubble Sort ar trebui să funcționeze cel puțin încă o dată. Pasul 3. Mai parcurgem matricea o data. Nimic de schimbat aici, așa că dacă folosim algoritmul Bubble Sort „îmbunătățit” (cu verificarea dacă a fost făcut cel puțin un schimb la pasul anterior), acest pas este ultimul.

Cod Java de sortare cu bule

Realizare Java sortare cu bule

Să creăm două metode pentru sortarea cu bule. Primul, bubbleSort(int[] myArray) este unul plan. Acesta rulează prin matrice de fiecare dată. Al doilea, optimizedBubbleSort(int myArray[]) este optimizat prin oprirea algoritmului dacă bucla interioară nu a provocat nicio schimbare. Contorul vă arată câți pași ați făcut în timpul sortării. Aici avem realizarea Java sortare cu bule:

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

Rezultatul funcționării algoritmului Java de sortare cu bule:

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]

Cât de eficient este sortarea cu bule?

Sortarea cu bule este unul dintre cei mai ușori algoritmi de implementat, dar nu este eficient. Este nevoie de o pereche de bucle imbricate. Chiar și într-o versiune optimizată a algoritmului în cel mai rău caz (fiecare element al setului de date este în ordine inversă celui dorit), bucla exterioară iterează o dată pentru fiecare dintre cele n elemente ale setului de date. Bucla interioară repetă de n ori pentru prima dată, ( n-1 ) pentru a doua și așa mai departe. Prin urmare, pentru a sorta toate n elementele, buclele trebuie executate de n*(n-1)/2 ori. Se numește O(n ² )complexitatea timpului și înseamnă că algoritmul face aproximativ 500 000 de comparații pentru 1000 de elemente ale unui tablou. Cu toate acestea, algoritmul de sortare cu bule este destul de eficient în utilizarea memoriei (complexitatea memoriei este O(n) ) și este foarte bun pentru seturi de date mici aproape sortate.