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]
GO TO FULL VERSION