Ordinamento a bolle Java

Se hai mai sentito parlare di metodi di ordinamento nella programmazione, molto probabilmente era l'algoritmo di ordinamento a bolle. È famoso. Ogni programmatore conosce il bubble sort (o almeno ne ha sentito parlare mentre impara) non perché sia ​​il miglior algoritmo di ordinamento al mondo, ma il più semplice. Questo algoritmo viene solitamente utilizzato per scopi di apprendimento o potresti ottenerlo come attività nella tua intervista Java Junior. L'algoritmo Java Bubble sort è molto facile da capire, tuttavia non è efficiente. Comunque, scopriamolo.

Cos'è l'ordinamento

Prima di tutto, devi capire cos'è l'ordinamento in generale e cosa possiamo ordinare nei programmi Java. Se possiamo confrontare due o più elementi o oggetti in base a uno qualsiasi dei loro attributi, significa che possono essere ordinati in base a questo attributo. Ad esempio, numeri in ordine crescente o decrescente o parole in ordine alfabetico. Pertanto, gli elementi devono essere confrontabili tra loro. A proposito, gli elementi di cosa? In Java, possiamo confrontare gli elementi di Collections. Ad esempio possiamo ordinare Array o ArrayList di interi, stringhe e così via.

Come funziona il Bubble Sort

Diciamo che dobbiamo ordinare un array di numeri interi in ordine crescente, cioè dal più piccolo al più grande. Per prima cosa, percorriamo l'intero array e confrontiamo ogni 2 elementi vicini. Se sono nell'ordine sbagliato (il vicino di sinistra è più grande di quello di destra), li scambiamo. Al primo passaggio alla fine apparirà l'elemento più grande (se ordiniamo in ordine crescente). Potresti dire che l'elemento più grande "si apre". Questo è il motivo del nome dell'algoritmo Bubble sort. Ripetiamo il primo passaggio dal primo al penultimo elemento. Abbiamo il secondo elemento più importante al penultimo posto. E così via. Possiamo migliorare un po' un algoritmo verificando se è stato effettuato almeno uno scambio nel passaggio precedente. In caso contrario, smettiamo di correre lungo l'array.

Esempio di ordinamento a bolle

Ordiniamo l'array di numeri interi, quello che puoi vedere sotto in un'immagine. Passaggio 1: stiamo esaminando l'array. L'algoritmo inizia con i primi due elementi (con indici 0 e 1), 8 e 7, e controlla se sono nell'ordine corretto. Ovviamente, 8 > 7, quindi li scambiamo. Successivamente, esaminiamo il secondo e il terzo elemento (indici 1 e 2), ora questi sono 8 e 1. Per gli stessi motivi, li scambiamo. Per la terza volta confrontiamo 8 e 2 e, almeno, 8 e 5. Abbiamo fatto quattro scambi in totale: (8, 7), (8, 1), (8, 2) e (8, 5). Un valore di 8, il più grande in questo array, è spuntato alla fine dell'elenco nella posizione corretta. Il risultato del primo passaggio del funzionamento dell'algoritmo Bubble sort è l'array successivo: Passaggio 2. Fare lo stesso con (7,1), (7,2) e (7,5). 7 è ora nella penultima posizione, e non abbiamo bisogno di confrontarlo con la "coda" dell'elenco, è già ordinato. Il risultato della seconda fase del funzionamento dell'algoritmo Bubble sort è l'array successivo: Come puoi vedere, questo array è già ordinato. Comunque l'algoritmo Bubble Sort dovrebbe funzionare almeno un'altra volta. Passaggio 3. Stiamo esaminando l'array ancora una volta. Niente da scambiare qui, quindi se stiamo usando l'algoritmo Bubble Sort "migliorato" (controllando se è stato effettuato almeno uno scambio nel passaggio precedente) questo passaggio è l'ultimo.

Codice Java di ordinamento a bolle

Bubble sort Realizzazione Java

Creiamo due metodi per Bubble sort. Il primo, bubbleSort(int[] myArray) è aereo. Esegue l'array ogni volta. Il secondo, optimizeBubbleSort(int myArray[]) è ottimizzato interrompendo l'algoritmo se il ciclo interno non ha causato alcuno scambio. Il contatore ti mostra quanti passi hai fatto durante l'ordinamento. Qui abbiamo la realizzazione Java di Bubble sort:

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

Il risultato del funzionamento dell'algoritmo Java Bubble sort:

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]

Quanto è efficiente il bubble sort?

Bubble sort è uno degli algoritmi più facili da implementare ma non è efficiente. Richiede un paio di cicli nidificati. Anche in una versione ottimizzata dell'algoritmo nel caso peggiore (ogni elemento del set di dati è in ordine inverso a quello desiderato) il ciclo esterno itera una volta per ciascuno degli n elementi del set di dati. Il ciclo interno itera n volte per la prima volta, ( n-1 ) per la seconda e così via. Quindi, per ordinare tutti gli n elementi, i cicli devono essere eseguiti n*(n-1)/2 volte. Chiama O(n ² )complessità temporale e significa che l'algoritmo esegue circa 500.000 confronti per 1000 elementi di un array. Tuttavia, l'algoritmo di ordinamento delle bolle è piuttosto efficace nell'utilizzo della memoria (la complessità della memoria è O(n) ) ed è davvero buono per piccoli set di dati quasi ordinati.