Java Algoritmi Di Ordinamento: Bubble Sort



Programmando, nasce spesso la necessità di ordinare le collezioni di dati o oggetti che devono poi essere manipolate. Ordinare una lista può essere utile nei casi in cui si debbano fare ricerche molto rapide. Vedremo più avanti quanto mantenere una lista ordinata sia utile per effettuare ricerche dicotomiche e avere quindi i risultati in un tempo nettamente minore rispetto ad una ricerca sequeziale.

Nel corso dell'articolo faremo riferimentro per la maggior parte del tempo ad array di interi. L'algoritmo è lo stesso nel caso in cui il tipo sia diverso.

Proprietà degli algoritmi

Questo è un discorso che farò ora e vale per tutti gli algoritmi di ordinamento di cui andremo a parlare nei prossimi articoli.

Generalmente, tutti gli algoritmi di ordinamento godono di proprietà utili a studiarli e soprattutto, per decidere quale sia il più consono alla situazione che si è presa in esame. Vediamo meglio.

Stabilità

Un algoritmo di ordinamento si dice stabile se preserva l'ordine relativo dei dati con chiavi uguali all'interno del file da ordinare. Ad esempio, se abbiamo in esame una lista di persone ordinate in ordine alfabetico, un algoritmo stabile restituirà sempre una lista ordinata in ordine alfabetico. Se l'algoritmo fosse instabile, si otterrebbe una lista senza alcuna traccia dell'ordinamento precedente.

Un possibile modo di forzare la stabilità dell'algoritmo è quello di aggiungere una chiave univoca ad ogni elemento. Questo principio viene ripreso anche in ambito database.

Sul posto o in-place

Un algoritmo si dice in-place se utilizza un numero costante di variabili per ordinare l'array e non usa array di supporto.

Adattività

Un algoritmo si definisce adattivo quando trae vantaggio dagli elementi già ordinati.

Andiamo ora ad analizzare in dettaglio alcune implementazioni di un algoritmo di ordinamento: il Bubble Sort.

Bubble Sort

Il bubble sort è un algoritmo di ordinamento di per sè non molto efficiente, utilizzato spesso a scopi didattici per introdurre il concetto di algoritmo di ordinamento.

Perchè "bubble sort"?

Il nome dell'algoritmo deriva dal suo comportamento. Infatti gli elementi del vettore si comportano esattamente come le bollicine in un calice di champagne: le più grandi salgono verso l'alto mentre quelle più piccole rimangono in basso, esattamente come mostra la gif qui sotto.

Bubble sort gif

Flow-chart

Flow chart

Implementazione

Precisiamo che il flow chart presenta una versione ottimizzata dell'algoritmo, mentre il codice qui sotto presenta la versione classica.

  public static void bubbleSort(int[] v) {  
          int n = v.length;  
          int temp = 0;  
           for(int index=0; index < n; index++){  
                   for(int j=1; j < (n-index); j++){  
                            if(v[j-1] > v[j]){  
                                   //scambia elementi
                                   temp = v[j-1];  
                                   v[j-1] = v[j];  
                                   v[j] = temp;  
                           }  
                   }  
           }  
}

Questa implementazione iterativa mostra esattamente il procedimento mostrato dalla gif. Infatti, andando a stampare passo passo i vari stati dell'array durante il processo di ordinamento, otterremo:

[6, 5, 3, 1, 8, 7, 2, 4]
[5, 3, 1, 6, 7, 2, 4, 8]
[3, 1, 5, 6, 2, 4, 7, 8]
[1, 3, 5, 2, 4, 6, 7, 8]
[1, 3, 2, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

Notiamo come il numero di passaggi che si devono fare per ordinare un array relativamente piccolo come quello dell'esempio sia veramente alto. Proprio per questo il bubble sort viene utilizzato fondamentalmente a scopi didattici a causa della sua inefficcienza. Proprio grazie alla predisposizione all'uso didattico, andiamo a fornire un'implementazione ricorsiva dello stesso algoritmo, definendo con swap il metodo che scambia due posizioni di uno stesso array.

    //metodo ricorsivo per implementare il bubble sort su un sottoarray
    public static void bubbleSort(int[] v, int n)
    {
        for (int index = 0; index < n - 1; index++) {
            if (arr[index] > arr[index + 1]) {
                swap(arr, index, index + 1);
            }
        }
        if (n - 1 > 1) {
            bubbleSort(arr, n - 1);
        }
    }

Il risultato ottenuto è lo stesso, ma cambia il modo in cui viene implementato.

Proprietà

Riprendendo il discorso sulle proprietà fatto in precedenza, possiamo tentare di identificare quali siano le proprietà del bubble sort.

Il bubble sort è stabile, infatti restituisce sempre un array ordinato crescentemente o decrescentemente indipendentemente dai dati presenti nella collezione.

E' in-place in quanto non utilizza array aggiuntivi per l'ordinamento.

E' adattivo, infatti nel caso in cui degli elementi siano ordinati, non effettua alcuna operazione e li lascia ordinati. Questa caratteristica permette di risparmiare un notevole numero di iterazioni.

Complessità

Facendo un discorso un po' più matematico, andiamo a vedere qualcosa sulla complessità dell'algoritmo. Facciamo una piccola premessa. La complessità si indica mediante i cosiddetti simboli di Landau, usati per paragonare l'andamento di due funzioni. Infatti si tende ad associare la complessità di un algoritmo ad una funzione, per poi paragonarla ad una nota.

Assumendo che la complessità di uno scambio sia O(1), la complessità dell'algoritmo è data dalla complessità dei cicli for annidati.

Nel caso migliore abbiamo una complessità pari a T(n)=n(n-1)/2  —> O(N²) mentre nel caso migliore l'array è già ordinato e quindi il numero di iterazioni è pari a 1.

Mediamente effettua circa N2 / 2 confronti ed altrettanti scambi.

Ottimizzazioni e conclusioni

Un primo modo di ottimizzare l'algoritmo si basa sul fatto che, se in una data iterazione n non si effettuano scambi, significa che l'array è ordinato e quindi l'algoritmo può terminare. Si fa ricorso quindi ad una variabile booleana che verifichi proprio questa condizione. Questo tipo di ottimizzazione è presentata nel flow chart sopra.

Una seconda linea di pensiero sostiene che se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore i, allora si può facilmente dimostrare che nessuna iterazione successiva eseguirà scambi in posizioni successive a tale valore i. L'ottimizzazione consiste nel memorizzare l'indice dove si è effettuato l'ultimo scambio e scandendo l'array fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo overhead.

Concludendo il discorso, possiamo dire che l'algoritmo si presta bene a fini didattici come detto prima. Non si presta bene ad ordinare array di grandi dimensioni.

Spezzando una lancia a suo favore, è facile da capire e implementare, non richiede un grande ammontare di memoria e la cosa più importante è che, una volta finito l'ordinamento, i dati sono pronti per l'elaborazione.

 
 
Alessio Mungelli

Alessio Mungelli

Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.

 
 
 

Articoli correlati

Un approccio a Java: Il ciclo while

Ciao a tutti e bentornati! Dopo aver fatto una breve, ma corposa, introduzione sui cicli, andiamo oggi a vedere finalmente le prime implementazioni che utilizzano quello che abbiamo definito ciclo precondizionale. In Java, come…

Un approccio a Java: I cicli - Introduzione

Ciao a tutti e bentornati! Sino ad ora, abbiamo parlato di variabili e di strutture di selezione, andando a considerare alcuni degli aspetti fondamentali di questi due concetti. Teoricamente, per…

Un approccio a Java: strutture di selezione - casi d'uso

Ciao a tutti e bentornati! Sino ad ora ci siamo preoccupati di fare una carrellata quanto più completa riguardo i concetti fondamentali di cui abbiamo bisogno per approcciarci all'utilizzo delle…

Un approccio a Java: operatori booleani

La volta precedente, abbiamo ampiamente parlato delle variabili booleane, cercando di delineare quali siano le principali operazioni che si possono effettuare proprio a livello pratico.  Di tutti i casi esaminati, non abbiamo…

Un approccio a Java: le variabili booleane

Ciao a tutti e bentornati! La volta precedente, ho fatto un'introduzione alle strutture condizionali, definendo il loro funzionamento. Prima di poter dare qualche esempio pratico, è necessario chiarire in che modo ci…

Un approccio a Java: strutture condizionali

Ciao a tutti e bentornati! Le volte precedenti abbiamo introdotto il concetto di variabile, tentando di definire alcuni concetti basilari a riguardo.  Alcune situazioni fanno però intuire come il solo concetto…

Un approccio a Java: Le variabili - caso d'uso

Ciao a tutti amici e bentornati! Dopo l'introduzione fatta sulle variabili, cerchiamo di analizzare alcune criticità che si possono presentare in situazioni alquanto comuni. Partiamo quindi analizzando degli esempi pratici.  Esempio 1: divisione…

Un approccio a Java: Le variabili

Ciao a tutti e bentornati! Quest'oggi inizieremo un percorso che ci porterà a studiare, ed eventualmente ripassare, quelle che sono le basi della programmazione. Inizieremo parlando di variaibli. Introduzione Chiunque voglia approcciarsi al…

Hashmap con concatenamento: liste di trabocco

In questa breve serie di articoli andremo a vedere com'è possibile realizzare in C la struttura dati Hashmap. Nell'implementazione andremo ad usare le liste doppiamente concatenate come strutture dati ausiliarie. Andiamo…

Google SEO: L'evoluzione delle anteprime nei risultati di ricerca

Google spiega i principi guida che stanno alla base delle anteprime dei risultati delle ricerche che hanno portato la pagina dei risultati dai 10 link blu a dove siamo oggi. Lo…

Java Strutture Dati: Liste Concatenate

Con il 2020 andiamo ad esaminare un nuovo aspetto della programmazione: le strutture dati. Spesso capita a tutti di utilizzare strutture messe a disposizione dai vari linguaggi di programmazione. L'obiettivo sarà…

Java Algoritmi di Ordinamento: Selection Sort

Andiamo oggi ad analizzare in dettaglio un algoritmo di ordinamento non molto efficiente ma piuttosto utilizzato in diversi ambiti. Stiamo parlando del Selection Sort. Vediamo meglio in dettaglio. Intuizione L'idea alla base è quella…

Utilizziamo i nostri cookie e quelli di terzi per migliorare i nostri servizi, compilare informazioni statistiche e analizzare le vostre abitudini di navigazione. Questo ci permette di personalizzare i contenuti che offriamo e di mostrarvi le pubblicità relative alle vostre preferenze. Cliccando su "Accetta tutto" acconsentite alla memorizzazione dei cookie sul vostro dispositivo per migliorare la navigazione del sito web, analizzare il traffico e assistere le nostre attività di marketing. Potete anche selezionare "Solo cookies di sistema" per accettare solo i cookies necessari al funzionamento del sito web, oppure potete selezionare i cookies che desiderate attivare cliccando su "Impostazioni". Tradotto con www.DeepL.com/Translator (versione gratuita)" o "Rifiuta".

Accetta tutti Solo cookies del sistema Configurazione