Bubble Algoritmo di ordinamento in Java: Programma ed esempio di ordinamento degli array
James Hartmann
⚡ Riepilogo intelligente
Bubble Algoritmo di ordinamento in Java confronta ripetutamente gli elementi adiacenti dell'array e li scambia finché la sequenza non è ordinata. Questo articolo spiega il meccanismo di funzionamento, lo pseudocodice, completo Java Implementazione, variante ottimizzata, analisi della complessità e confronti pratici con altre tecniche di ordinamento.
Cosa è Bubble Ordina?
BubbleSort è un semplice algoritmo di ordinamento basato sul confronto che confronta il primo elemento di un array con il successivo. Se l'elemento corrente dell'array è numericamente maggiore del successivo, gli elementi vengono scambiati. Allo stesso modo, l'algoritmo scorrerà tutti gli elementi dell'array.
L'algoritmo prende il nome dal modo in cui il valore più grande nella regione non ordinata sale costantemente fino alla sua posizione finale, proprio come una bolla che sale in superficie. Dopo il primo passaggio completo, l'elemento più grande occupa l'ultimo indice. Dopo il secondo passaggio, il secondo elemento più grande viene bloccato in posizione e il processo si ripete finché l'array non è completamente ordinato.
In questo articolo creeremo un Java programma da implementare BubblOrdina. Controlla l'output del codice che ti aiuterà a comprendere la logica del programma, quindi rivedi la versione ottimizzata e l'analisi della complessità che seguono.
Come fa il BubblL'algoritmo di ordinamento funziona?
Bubble L'ordinamento funziona tramite passaggi ripetuti sull'array. Ogni passaggio va dal primo indice alla fine della regione attualmente non ordinata, confrontando i valori vicini e scambiandoliping li elimina ogni volta che appaiono nell'ordine sbagliato. Poiché il valore rimanente più grande si sposta sempre all'estrema destra della regione non ordinata, la regione si riduce esattamente di una posizione dopo ogni passaggio.
L'intero processo può essere suddiviso in quattro fasi ripetibili:
- Confronta: Esamina l'elemento all'indice j-1 rispetto all'elemento all'indice j.
- Scambiare: Se l'elemento a sinistra è maggiore dell'elemento a destra, scambia i due valori utilizzando una variabile temporanea.
- Progredire: Spostati di una posizione a destra e ripeti l'operazione finché non raggiungi la fine della regione non ordinata.
- Ripetere: Avvia un nuovo passaggio su una regione che è più corta di un elemento e interrompi dopo n-1 passaggi o quando un passaggio non effettua alcuno scambio.
La tabella qui sotto tracSi tratta dell'array di esempio {860, 8, 200, 9} utilizzato nel programma più avanti in questa pagina. Mostra esattamente quale valore si stabilizza nella sua posizione finale al termine di ogni passaggio.
| Passare | Array all'inizio del passaggio | Confronti effettuati | Array alla fine del passaggio | Elemento bloccato |
|---|---|---|---|---|
| 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 |
Si noti che il terzo passaggio esegue un confronto ma non uno scambio. Un'implementazione ottimizzata rileva questa condizione e si arresta immediatamente, il che rappresenta il miglioramento più prezioso che si possa apportare a questo algoritmo.
BubblPseudocodice dell'algoritmo di ordinamento e
Prima di scrivere Java La sintassi aiuta a esprimere la logica in pseudocodice indipendente dal linguaggio. La versione seguente include il flag di uscita anticipata, quindi copre sia il comportamento classico che quello ottimizzato.
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
Il ciclo esterno controlla il numero di passaggi, mentre il ciclo interno controlla i confronti all'interno di un singolo passaggio. Il limite superiore del ciclo interno è n – i – 1 perché le ultime i posizioni hanno già i loro valori finali.
Java Programma da implementare Bubble Ordina
Il seguente programma ordina un array di interi in ordine crescente. Le istruzioni print aggiuntive sono state mantenute all'interno dei cicli appositamente, perché la lettura del passaggio per passaggio trace è il modo più rapido per un principiante di capire come si accumulano gli swap.
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(); } }
Produzione:
---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 spiegazione: Migliori BubbleSort Il metodo riceve l'array per riferimento, quindi il chiamante vede il risultato ordinato senza alcun valore di ritorno. La variabile Temp. mantiene un valore durante lo scambio di tre righe, motivo per cui l'algoritmo necessita solo di O(1) memoria aggiuntiva. L'espressione n – i nella condizione del ciclo interno si garantisce che le posizioni già ordinate in coda non vengano mai più visitate.
Ottimizzato Bubble Ordina programma in Java
Il programma sopra riportato esegue sempre n-1 passaggi, anche quando l'array risulta ordinato prematuramente. L'aggiunta di un singolo flag booleano risolve questa inefficienza. Se un passaggio completo termina senza alcuno scambio, l'array è garantito essere ordinato e il ciclo esterno può interrompersi immediatamente.
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); } }
Produzione:
Passes executed: 1 [5, 12, 33, 47, 58]
L'array di input era già ordinato, quindi la versione ottimizzata ha terminato dopo un singolo passaggio invece di quattro. Su dati quasi ordinati, questa modifica trasforma un carico di lavoro quadratico in uno quasi lineare, che è il motivo principale Bubble L'algoritmo Sort compare ancora di tanto in tanto nel codice reale.
Complessità temporale e spaziale di Bubble Ordina
La complessità descrive come il tempo di esecuzione aumenta all'aumentare della dimensione dell'input. Per Bubble L'ordinamento del conteggio dei confronti nella versione non ottimizzata è fissato a n(n-1)/2, il che lo colloca saldamente nella classe quadratica.
| Scenario | Condizione di input | Complessità temporale | Complessità spaziale |
|---|---|---|---|
| caso migliore | Array già ordinato, versione ottimizzata | O (n) | O (1) |
| Caso medio | Elementi in ordine casuale | O(n²) | O (1) |
| Caso peggiore | Array ordinato in ordine inverso | O(n²) | O (1) |
Poiché ogni scambio avviene all'interno dell'array originale e viene utilizzata una sola variabile temporanea, Bubble Sort è un algoritmo in-place con spazio ausiliario O(1). È anche un ordinamento stabile, il che significa che due record che possiedono la stessa chiave mantengono il loro ordine relativo originale dopo l'ordinamento.
Vantaggi e svantaggi di Bubble Ordina
Comprendere entrambi i punti di vista aiuta a decidere quando l'algoritmo rappresenta una scelta accettabile e quando dovrebbe essere sostituito.
Vantaggi
- Semplicità: La logica si sviluppa in circa dieci righe, il che rende facile scriverla correttamente anche durante un colloquio.
- Funzionamento in loco: Non viene allocato alcun array ausiliario, quindi l'utilizzo della memoria non aumenta con la dimensione dell'input.
- Stabilità: Le chiavi uguali mantengono il loro ordine originale, il che è importante quando si ordinano i record in base a un campo secondario.
- Rilevamento precoce dell'uscita: Il flag "scambiato" identifica un array già ordinato in un singolo passaggio.
Svantaggi
- Crescita quadratica: Ordinare 10,000 elementi richiede, nel caso peggiore, quasi 50 milioni di confronti.
- Scrive eccessivamente: L'algoritmo esegue molti più scambi rispetto all'ordinamento per selezione, che è dispendioso in termini di memoria e presenta operazioni di scrittura lente.
- Scarsa scalabilità: Nei carichi di lavoro di produzione, si prediligono quasi sempre Quicksort, Merge Sort o il metodo integrato Arrays.sort.
Suggerimento: In produzione Java codice, preferisco Arrays.sort () per i primitivi e Collections.sort() per gli elenchi. Entrambi utilizzano algoritmi altamente ottimizzati, rispettivamente Dual-Pivot Quicksort e TimSort, che superano le prestazioni di un algoritmo scritto a mano. Bubble Ordina per ordini di grandezza.
Bubble Sort vs. Altri metodi di ordinamento Algorithms
La tabella sottostante mette a confronto Bubble Ordina con le tecniche di ordinamento che i principianti incontreranno in seguito, così potrai vedere esattamente dove ognuna risulta più efficace.
| Algoritmo | Caso migliore | Caso medio | Caso peggiore | lo spazio | Stabile |
|---|---|---|---|---|---|
| Bubble Ordina | O (n) | O(n²) | O(n²) | O (1) | Si |
| Ordina selezione | O(n²) | O(n²) | O(n²) | O (1) | Non |
| Ordinamento di inserzione | O (n) | O(n²) | O(n²) | O (1) | Si |
| quicksort | O (n log n) | O (n log n) | O(n²) | O (log n) | Non |
| Ordinamento heap | O (n log n) | O (n log n) | O (n log n) | O (1) | Non |
Bubble Sort e Insertion Sort condividono lo stesso caso migliore lineare, ma Insertion Sort esegue meno scambi su dati parzialmente ordinati. Selection Sort esegue sempre esattamente n-1 scambi, il che lo rendetracUtile quando le operazioni di scrittura sono costose, anche se ciò compromette la stabilità. Per qualsiasi array di dimensioni superiori a poche centinaia di elementi, Quicksort o Heap Sort sono la scelta corretta.
Una volta che hai familiarità con i modelli di attraversamento degli array utilizzati qui, la stessa struttura di ciclo appare in molti esercizi classici come il serie di Fibonacci in Java e Java programma palindromo. Revvista Java array e il più ampio Java lezione rafforzerà i principi fondamentali su cui si basa questo algoritmo.
