Introduzione a Bubble Sort in Java
Bubble sort è uno degli algoritmi più comunemente usati per ordinare i dati in Java. L'ordinamento qui viene effettuato confrontando ricorsivamente i numeri adiacenti e spostandoli nell'ordine crescente o decrescente, come richiesto. Questo spostamento di elementi viene eseguito fino a quando tutte le cifre non vengono completamente ordinate nell'ordine richiesto.
Il nome "Bubble sort" di questo algoritmo è perché gli elementi di un array si fanno strada verso l'inizio. Cerchiamo di capire l'algoritmo di ordinamento delle bolle prendendo un esempio.
Esempio: considerare una matrice di numeri (6 1 8 5 3) che devono essere disposti in ordine crescente.
L'algoritmo di ordinamento a bolle funziona in più iterazioni fino a quando non rileva che tutti i numeri sono ordinati.
iterazioni
Di seguito sono riportate le iterazioni eseguite in Bubble Sort in Java, che è la seguente:
Prima Iterazione
(6 1 8 5 3) - Inizia confrontando i primi due numeri e sposta il numero minore dei due alla sua destra. Quindi tra 6 e 1, 1 è il numero più piccolo spostato a sinistra e 6 a destra. (1 6 8 5 3) - Successivamente confronta i due numeri adiacenti spostando una posizione verso destra. Qui, il numero 6 è inferiore a 8 e quindi viene mantenuto lo stesso ordine. (1 6 8 5 3) - Spostando di nuovo una posizione verso destra, il confronto ha luogo tra 8 e 5. Il numero 5 viene spostato a sinistra poiché è inferiore a 8. (1 6 5 8 3) - Qui il confronto avviene tra i numeri 8 e 3. Il numero 3 viene spostato a sinistra poiché è inferiore a 8. (1 6 5 3 8) - Questo è il risultato finale dell'ordine dopo la prima iterazione.Seconda Iterazione
Poiché i numeri non sono ancora completamente nel loro ordine crescente, il programma procede per la seconda iterazione.
(1 6 5 3 8) - Qui il confronto ricomincia dalle prime due cifre del risultato dalla prima iterazione. Confronta i numeri 1 e 6 e mantiene lo stesso ordine poiché 1 è inferiore a 6. (1 6 5 3 8) - Qui vengono confrontati i numeri 5 e 6. Lo stesso ordine viene mantenuto in quanto è già nell'ordine crescente richiesto. (1 5 6 3 8) - Qui il confronto avviene tra i numeri 6 e 3. Il numero 3 viene spostato a sinistra poiché è inferiore a 6. (1 5 3 6 8) - I successivi numeri 6 e 8 vengono confrontati tra loro. Lo stesso ordine viene mantenuto come in un ordine previsto. (1 5 3 6 8) - Questo è il risultato finale dopo la seconda iterazione. Tuttavia, possiamo notare che le cifre non sono completamente disposte nel loro ordine crescente. Dobbiamo ancora scambiare i numeri 5 e 3 per ottenere il risultato finale. Quindi il programma va per la terza iterazione.Terza Iterazione
(1 5 3 6 8) - La terza iterazione inizia confrontando le prime due cifre 1 e 5. Poiché l'ordine è come previsto, viene mantenuto lo stesso. (1 5 3 6 8) - Successivamente vengono confrontati i numeri adiacenti 3 e 5. Poiché 5 è più grande di 3, viene spostato sul lato destro. (1 3 5 6 8) - L'iterazione continua a confrontare i numeri 5 e 6, 6 e 8. Poiché è nell'ordine richiesto, mantiene l'ordine. (1 3 5 6 8) - Infine, l'iterazione viene interrotta mentre il programma attraversa confrontando ciascun elemento adiacente e scopre che tutte le cifre sono in ordine crescente.Dato che qui c'erano solo 5 elementi di un array che dovevano essere ordinati, sono state impiegate solo 3 iterazioni in totale. All'aumentare degli elementi nell'array, aumenta anche la quantità di iterazioni.
Implementazione dell'ordinamento a bolle usando Java
Di seguito è riportato il codice Java che è l'implementazione dell'algoritmo di ordinamento Bubble. (Si noti che la prima posizione di un array in Java inizia da 0 e continua con incrementi di 1, cioè array (0), array (1), array (2) e continua.)
Codice:
import java.util.Scanner;
public class BubbleSort (
static void bubbleSort(int() arraytest) (
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++)( // first for loop performs multiple iterations
for(int j=1; j < (ni); j++)(
if(arraytest(j-1) > arraytest(j))( // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest(j-1); // assigns the greater number to temp variable
arraytest(j-1) = arraytest(j); // shifts the lesser number to the previous position
arraytest(j) = temp; // bigger number is then assigned to the right hand side
)
)
)
)
public static void main(String() args) (
int arraytest() =(23, 16, 3, 42, 75, 536, 61); // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)( // for loop used to print the values of array
System.out.print(arraytest(i) + " ");
)
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++)(
System.out.print(arraytest(i) + " "); // for loop to print output values from array
)
)
)
Produzione:
Vantaggi e svantaggi di Bubble Sort in Java
Di seguito sono riportati i diversi vantaggi e svantaggi dell'ordinamento delle bolle in Java:
vantaggi
- Il codice è molto facile da scrivere e da capire. In genere richiede solo pochi minuti.
- Anche l'implementazione è molto semplice.
- L'ordinamento a bolle ordina i numeri e li mantiene in memoria, risparmiando così molta memoria.
svantaggi
- Questo algoritmo non è adatto a set di dati di grandi dimensioni poiché il confronto richiede molto tempo. Il tempo necessario per ordinare i numeri di input aumenta in modo esponenziale.
- O (n 2) è la complessità media di Bubble sort e O (n) è la complessità del caso migliore (il caso migliore è quando gli elementi sono ordinati in primo luogo) dove n è il numero di elementi.
Applicazioni in tempo reale
Dal momento che Bubble sort è in grado di rilevare piccoli errori nell'ordinamento, viene utilizzato nella computer grafica. Viene anche utilizzato nell'algoritmo di riempimento del poligono in cui è necessario ordinare il rivestimento dei vertici del poligono.
Conclusione
In questo articolo, abbiamo visto come funziona l'algoritmo di ordinamento Bubble e come può essere implementato usando la programmazione Java. Bubble sort è un algoritmo molto stabile che può essere facilmente implementato per set di dati relativamente piccoli. È un caso di algoritmo di confronto ed è utilizzato dai novizi per la sua semplicità.
Articoli consigliati
Questa è una guida per Bubble Sort in Java. Qui discutiamo più iterazioni per eseguire il bubble sort in java e la sua implementazione del codice insieme a vantaggi e svantaggi. Puoi anche consultare i seguenti articoli per saperne di più -
- Bubble Ordina in JavaScript
- Ordinamento in R
- Matrici 3D in Java
- Matrici in C #
- Bubble Sort in Python