Bubble Sort in Java

1. Introduzione

In questo rapido articolo, esploreremo in dettaglio l'algoritmo Bubble Sort, concentrandoci su un'implementazione Java.

Questo è uno degli algoritmi di ordinamento più semplici; l'idea centrale è di continuare a scambiare elementi adiacenti di un array se sono in un ordine errato fino a quando la raccolta non viene ordinata.

I piccoli elementi "bolla" all'inizio dell'elenco mentre iteriamo la struttura dei dati. Quindi, la tecnica è nota come Bubble sort.

Poiché l'ordinamento viene eseguito tramite scambio, possiamo dire che esegue l'ordinamento sul posto.

Inoltre, se due elementi hanno gli stessi valori, i dati risultanti avranno il loro ordine conservato , il che lo rende un ordinamento stabile.

2. Metodologia

Come accennato in precedenza, per ordinare un array, lo iteriamo confrontando gli elementi adiacenti e, se necessario, scambiandoli. Per un array di dimensione n , eseguiamo n-1 tali iterazioni.

Facciamo un esempio per capire la metodologia. Vorremmo ordinare l'array in ordine crescente:

4 2 1 6 3 5

Iniziamo la prima iterazione confrontando 4 e 2; non sono decisamente nell'ordine corretto. Lo scambio comporterebbe:

[2 4] 1 6 3 5

Ora, ripetendo lo stesso per 4 e 1:

2 [1 4] 6 3 5

Continuiamo a farlo fino alla fine:

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

Come possiamo vedere, alla fine della prima iterazione, abbiamo ottenuto l'ultimo elemento al suo posto legittimo. Ora, tutto ciò che dobbiamo fare è ripetere la stessa procedura in ulteriori iterazioni. Tranne, escludiamo gli elementi che sono già ordinati.

Nella seconda iterazione, itereremo sull'intero array ad eccezione dell'ultimo elemento. Allo stesso modo, per la terza iterazione, omettiamo gli ultimi 2 elementi. In generale, per l'iterazione k-esima, iteriamo fino all'indice nk (escluso). Alla fine di n-1 iterazioni, otterremo l'array ordinato.

Ora che hai compreso la tecnica, tuffiamoci nell'implementazione.

3. Implementazione

Implementiamo l'ordinamento per l'array di esempio di cui abbiamo discusso utilizzando l'approccio Java 8:

void bubbleSort(Integer[] arr) { int n = arr.length; IntStream.range(0, n - 1) .flatMap(i -> IntStream.range(1, n - i)) .forEach(j -> { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } }); }

E un rapido test JUnit per l'algoritmo:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }

4. Complessità e ottimizzazione

Come possiamo vedere, per la media e il caso peggiore , la complessità temporale è O (n ^ 2) .

Inoltre, la complessità dello spazio , anche nello scenario peggiore, è O (1) poiché l'algoritmo di Bubble sort non richiede memoria aggiuntiva e l'ordinamento avviene nell'array originale.

Analizzando attentamente la soluzione, possiamo vedere che se non vengono trovati swap in un'iterazione, non è necessario iterare ulteriormente .

Nel caso dell'esempio discusso in precedenza, dopo la 2a iterazione, otteniamo:

1 2 3 4 5 6

Nella terza iterazione, non è necessario scambiare nessuna coppia di elementi adiacenti. Quindi possiamo saltare tutte le iterazioni rimanenti.

Nel caso di un array ordinato, lo scambio non sarà necessario nella prima iterazione stessa, il che significa che possiamo interrompere l'esecuzione. Questo è lo scenario migliore e la complessità temporale dell'algoritmo è O (n) .

Ora implementiamo la soluzione ottimizzata.

public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (int j = 1; j  arr[j]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; swapNeeded = true; } } if(!swapNeeded) { break; } i++; } }

Controlliamo l'output per l'algoritmo ottimizzato:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }

5. conclusione

In questo tutorial, abbiamo visto come funziona Bubble Sort e la sua implementazione in Java. Abbiamo anche visto come può essere ottimizzato. Per riassumere, è un algoritmo stabile sul posto, con complessità temporale:

  • Caso peggiore e medio: O (n * n), quando l'array è in ordine inverso
  • Caso migliore: O (n), quando l'array è già ordinato

L'algoritmo è popolare nella computer grafica, grazie alla sua capacità di rilevare alcuni piccoli errori nell'ordinamento. Ad esempio, in un array quasi ordinato, solo due elementi devono essere scambiati, per ottenere un array completamente ordinato. Bubble Sort può correggere tali errori (es. Ordinare questo array) in tempo lineare.

Come sempre, il codice per l'implementazione di questo algoritmo può essere trovato su GitHub.