Bubble Sortare algoritm în Java: Program de sortare a matricei și exemplu
James Hartman
⚡ Rezumat inteligent
Bubble Sortare algoritm în Java compară în mod repetat elementele adiacente ale tabloului și le schimbă până când secvența este ordonată. Acest articol explică mecanismul de funcționare, pseudocodul, complet Java implementare, variante optimizate, analiza complexității și comparații practice cu alte tehnici de sortare.
Ce Este Bubble Sort?
Bubble Sort este un algoritm simplu de sortare bazat pe comparații care compară primul element al tabloului cu următorul. Dacă elementul curent al tabloului este numeric mai mare decât următorul, elementele sunt inversate. În mod similar, algoritmul va parcurge întregul element al tabloului.
Algoritmul își ia numele de la modul în care cea mai mare valoare din regiunea nesortată crește constant până la poziția sa finală, la fel ca o bulă care se ridică la suprafața apei. După prima trecere completă, cel mai mare element ocupă ultimul index. După a doua trecere, al doilea element ca mărime este blocat în poziție, iar procesul se repetă până când matricea este complet ordonată.
În acest articol, vom crea un Java program de implementat Bubble Sortare. Verificați rezultatul codului care vă va ajuta să înțelegeți logica programului, apoi examinați versiunea optimizată și analiza complexității care urmează.
Cum funcționează BubblFuncționează algoritmul de sortare e?
BubblSortarea funcționează prin treceri repetate asupra matricei. Fiecare trecere parcurge de la primul index până la sfârșitul regiunii nesortate în prezent, comparând valorile vecine și schimbând valorile.ping le ori de câte ori apar în ordine greșită. Deoarece cea mai mare valoare rămasă se deplasează întotdeauna în extrema dreaptă a regiunii nesortate, regiunea se micșorează cu exact o poziție după fiecare trecere.
Procesul complet poate fi împărțit în patru etape repetitive:
- Comparaţie: Examinați elementul de la indicele j-1 în raport cu elementul de la indicele j.
- Swap: Dacă elementul din stânga este mai mare decât elementul din dreapta, cele două valori se schimbă folosind o variabilă temporară.
- Avans: Mutați o poziție la dreapta și repetați până când se ajunge la sfârșitul regiunii nesortate.
- Repeta: Începeți o nouă trecere peste o regiune care este mai scurtă cu un element și opriți-o după n-1 treceri sau când o trecere nu efectuează nicio schimbare.
Tabelul de mai jos tracreprezintă matricea exemplu {860, 8, 200, 9} utilizată în programul de mai jos pe această pagină. Arată exact ce valoare se stabilizează în poziția finală la sfârșitul fiecărei treceri.
| Trece | Matrice la începutul trecerii | Comparații efectuate | Matrice la sfârșitul trecerii | Element blocat |
|---|---|---|---|---|
| 1 | 860, 8, 200, 9 | 3 | 8, 200, 9, 860 | 860 |
| 2 | 8, 200, 9, 860 | 2 | 8, 9, 200, 860 | 200 |
| 3 | 8, 9, 200, 860 | 1 | 8, 9, 200, 860 | 9 |
| 4 | 8, 9, 200, 860 | 0 | 8, 9, 200, 860 | 8 |
Observați că a treia trecere efectuează o comparație, dar nu și o schimbare. O implementare optimizată detectează această condiție și se oprește imediat, aceasta fiind cea mai valoroasă îmbunătățire pe care o puteți aplica acestui algoritm.
BubblPseudocod al algoritmului de sortare e
Înainte de a scrie Java sintaxă, ajută la exprimarea logicii în pseudocod neutru din punct de vedere al limbajului. Versiunea de mai jos include indicatorul de ieșire timpurie, deci acoperă atât comportamentul clasic, cât și pe cel optimizat.
procedure bubbleSort(array A, integer n) for i from 0 to n - 2 do swapped := false for j from 1 to n - i - 1 do // compare the adjacent pair if A[j - 1] > A[j] then swap A[j - 1] and A[j] swapped := true end if end for // no swap in a full pass means the array is sorted if swapped = false then break end if end for end procedure
Bucla externă controlează numărul de treceri, iar bucla interioară controlează comparațiile din cadrul unei singure treceri. Limita superioară a buclei interne este n – i – 1 deoarece ultimele i poziții își mențin deja valorile finale.
Java Program de implementat Bubble Sortare
Următorul program sortează un tablou de numere întregi în ordine crescătoare. Instrucțiunile de imprimare suplimentare au fost păstrate intenționat în interiorul buclelor, deoarece citirea datelor de trecere prin bypass trace este cea mai rapidă modalitate pentru un începător de a înțelege cum se acumulează swap-urile.
package com.guru99; public class BubbleSort { public static void main(String[] args) { int arr[] = {860, 8, 200, 9}; System.out.println("---Array BEFORE Bubble Sort---"); printArray(arr); bubbleSort(arr); //sorting array elements using bubble sort System.out.println("---Array AFTER Bubble Sort---"); printArray(arr); } static void bubbleSort(int[] array) { int n = array.length; int temp = 0; for(int i = 0; i < n; i++) // Looping through the array length { System.out.println("Sort Pass Number " + (i + 1)); for(int j = 1; j < (n - i); j++) { System.out.println("Comparing " + array[j - 1] + " and " + array[j]); if(array[j - 1] > array[j]) { //swap elements temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; System.out.println(array[j] + " is greater than " + array[j - 1]); System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } } } static void printArray(int[] array){ for(int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
ieșire:
---Array BEFORE Bubble Sort--- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Swapping Elements: New Array After Swap 8 860 200 9 Comparing 860 and 200 860 is greater than 200 Swapping Elements: New Array After Swap 8 200 860 9 Comparing 860 and 9 860 is greater than 9 Swapping Elements: New Array After Swap 8 200 9 860 Sort Pass Number 2 Comparing 8 and 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 8 and 9 Sort Pass Number 4 ---Array AFTER Bubble Sort--- 8 9 200 860
Code explicaţie: Sortare cu bule Metoda primește matricea prin referință, astfel încât apelantul vede rezultatul sortat fără nicio valoare returnată. Variabila temp păstrează o valoare în timpul schimbării a trei linii, motiv pentru care algoritmul are nevoie doar de O(1) memorie suplimentară. Expresia n – i în condiția buclei interioare garantează că pozițiile deja sortate la coadă nu sunt niciodată revizitate.
Optimizat Bubble Sortați programul în Java
Programul de mai sus efectuează întotdeauna n-1 pase, chiar și atunci când matricea este sortată mai devreme. Adăugarea unui singur indicator boolean remediază această ineficiență. Dacă o pasă completă se termină fără o singură schimbare, este garantat că matricea va fi sortată, iar bucla exterioară se poate opri imediat.
package com.guru99; public class OptimizedBubbleSort { public static void main(String[] args) { int arr[] = {5, 12, 33, 47, 58}; bubbleSort(arr); System.out.println(java.util.Arrays.toString(arr)); } static void bubbleSort(int[] array) { int n = array.length; int passes = 0; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 1; j < n - i; j++) { if (array[j - 1] > array[j]) { int temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; swapped = true; } } passes++; // Early exit: the array is already sorted if (!swapped) { break; } } System.out.println("Passes executed: " + passes); } }
ieșire:
Passes executed: 1 [5, 12, 33, 47, 58]
Matricea de intrare era deja sortată, așadar versiunea optimizată s-a terminat după o singură trecere în loc de patru. Pe date aproape sortate, această modificare transformă o sarcină de lucru pătratică într-una aproape liniară, acesta fiind principalul motiv pentru care BubblFuncția e Sort încă apare din când în când în codul real.
Complexitatea timpului și complexitatea spațiului Bubble Sortare
Complexitatea descrie modul în care timpul de execuție crește pe măsură ce dimensiunea intrării crește. Pentru BubblSortarea e Numărul de comparații în versiunea neoptimizată este fixat la n(n-1)/2, ceea ce o plasează ferm în clasa pătratică.
| Scenariu | Condiție de intrare | Complexitatea timpului | Complexitatea spațială |
|---|---|---|---|
| Cel mai bun caz | Matrice deja sortată, versiune optimizată | O (n) | O (1) |
| Caz mediu | Elemente în ordine aleatorie | O(n²) | O (1) |
| Cel mai rău caz | Matrice sortată în ordine inversă | O(n²) | O (1) |
Deoarece fiecare schimb are loc în interiorul matricei originale și se folosește o singură variabilă temporară, Bubble Sort este un algoritm in-place cu spațiu auxiliar O(1). De asemenea, este o sortare stabilă, ceea ce înseamnă că două înregistrări care dețin aceeași cheie își păstrează ordinea relativă originală după sortare.
Avantajele și dezavantajele Bubble Sortare
Înțelegerea ambelor părți te ajută să decizi când algoritmul este o alegere acceptabilă și când ar trebui înlocuit.
Avantaje
- Simplitate: Logica se încadrează în aproximativ zece rânduri, ceea ce facilitează scrierea corectă în condiții de interviu.
- Operare la fața locului: Nu este alocată nicio matrice auxiliară, deci utilizarea memoriei nu crește odată cu dimensiunea intrării.
- Stabilitate: Cheile egale își păstrează ordinea originală, ceea ce este important atunci când se sortează înregistrările după un câmp secundar.
- Detectarea timpurie a ieșirii: Indicatorul swapped identifică o matrice deja sortată într-o singură trecere.
Dezavantaje
- Creștere pătratică: Sortarea a 10,000 de elemente necesită aproape 50 de milioane de comparații în cel mai rău caz.
- Scrieri excesive: Algoritmul efectuează mult mai multe schimbări decât sortarea prin selecție, care este costisitoare din punct de vedere al memoriei, având operațiuni de scriere lente.
- Scalabilitate slabă: Volumurile de lucru de producție favorizează aproape întotdeauna Quicksort, Merge Sort sau metoda încorporată Arrays.sort.
💡 Sfat: In productie Java cod, preferă Arrays.sort () pentru primitive și Colecții.sort() pentru liste. Ambele utilizează algoritmi extrem de optimizați, Dual-Pivot Quicksort și respectiv TimSort, care depășesc performanța unui formular scris de mână Bubble Sortați după ordine de mărime.
BubblSortare electronică vs. alte metode de sortare Algorithms
Tabelul de mai jos compară BubblSortează folosind tehnicile de sortare pe care începătorii le întâlnesc în continuare, astfel încât să poți vedea exact unde câștigă fiecare.
| Algoritm | Cel mai bun caz | Caz mediu | Cel mai rău caz | Spaţiu | Stabil |
|---|---|---|---|---|---|
| Bubble Sortare | O (n) | O(n²) | O(n²) | O (1) | Da |
| Selecție Sortare | O(n²) | O(n²) | O(n²) | O (1) | Nu |
| Sortare prin inserție | O (n) | O(n²) | O(n²) | O (1) | Da |
| Sortare rapida | O (n jurnal n) | O (n jurnal n) | O(n²) | O (jurnal n) | Nu |
| Sortare în grămadă | O (n jurnal n) | O (n jurnal n) | O (n jurnal n) | O (1) | Nu |
BubblSortarea prin e și sortarea prin inserție au același caz ideal liniar, dar sortarea prin inserție efectuează mai puține schimbări pe datele parțial sortate. Sortarea prin selecție efectuează întotdeauna exact n-1 schimbări, ceea ce o face latractivă atunci când scrierile sunt costisitoare, deși sacrifică stabilitatea. Pentru orice matrice mai mare de câteva sute de elemente, Quicksort sau Heap Sort este alegerea corectă.
Odată ce vă familiarizați cu modelele de traversare a matricelor utilizate aici, aceeași structură de buclă apare în multe exerciții clasice, cum ar fi Seria Fibonacci în Java si Java program palindrom. Revprivind Java matrice și cu atât mai larg Java tutorial va consolida elementele fundamentale de care depinde acest algoritm.
