Dopo aver parlato della complessità computazionale e della ricerca di un elemento in un array, oggi parleremo dell’ordinamento di un array.
Data una sequenza di elementi sotto forma di array, la si vuole ordinare in maniera crescente o decrescente in base ad una certa relazione d’ordine (presi due elementi a scelta, deve sempre essere possibile accertare quale venga prima e quale dopo).
Nel corso dell’articolo si farà riferimento ad array di tipo numerico ed, in particolare, di tipo intero e si prenderà in considerazione l’ordinamento di tipo crescente. Solitamente, per ottenere la variante con ordinamento decrescente, sono sufficienti delle piccole modifiche.
Sebbene sarà indicata la complessità computazionale nel caso medio di ciascun algoritmo, il suo valore non sarà analizzato perché le dimostrazioni matematiche necessarie sono complesse e vanno aldilà dello scopo di questo articolo.
Argomenti trattati:
PROPRIETÀ DEGLI ALGORITMI
Esistono delle proprietà che caratterizzano gli algoritmi di ordinamento e che possono essere utili per studiarli o per decidere quale algoritmo adoperare in un determinato caso.
STABILITÀ
Un algoritmo di ordinamento è stabile quando mantiene l’ordine originale degli oggetti con chiavi uguali. Se ad esempio si vuole ordinare una lista di nominativi per cognome e la lista è già stata ordinata per nome, utilizzando un algoritmo stabile l’ordinamento dei nomi verrà rispettato come in un classico elenco telefonico. Diversamente, le persone con lo stesso cognome sarebbero disposte “casualmente” rispetto al nome.
SUL POSTO (IN-PLACE)
Un algoritmo di ordinamento si dice sul posto se utilizza un numero costante di variabili oltre all’array da ordinare e non utilizza quindi un array di supporto.
ADATTIVITÀ
Un algoritmo di ordinamento è adattivo quando trae vantaggio dagli elementi già ordinati.
BUBBLE SORT
Il bubble sort è un semplice algoritmo di ordinamento non molto efficiente. Difatti, si utilizza a scopi didattici grazie alla sua semplicità e per introdurre gli sviluppatori agli algoritmi ed alla complessità computazionale.
L’algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati: quelli più piccoli “risalgono” verso un’estremità della lista, mentre quelli più grandi “affondano” verso l’estremità opposta, come le bolle in un bicchiere di spumante.
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for(int i=0; i<n; i++) {
swapped = false;
for(int j=1; j<(n-i); j++)
if(arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
swapped = true;
}
if (!swapped)
break;
}
}
Ad ogni iterazione, si considerano, una ad una, tutte le possibili coppie di elementi adiacenti, scambiandoli se risultano nell’ordine errato. Dopo ogni iterazione, l’elemento massimo è in fondo alla parte di array considerata. Grazie all’utilizzo della variabile swapped, è possibile ottimizzare l’algoritmo fermandone l’esecuzione se il ciclo for più interno non ha effettuato alcuno scambio.
PROPRIETà
COMPLESSITÀ COMPUTAZIONALE
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione variabile, confronto ed incremento di un valore intero hanno un tempo di esecuzione pari ad O(1). Il tempo di esecuzione dell’algoritmo è dato dalla complessità del corpo dei cicli for annidati per il numero di volte in cui essi vengono eseguiti.
- Caso peggiore: l’array è ordinato in maniera inversa; la prima iterazione effettuerà n controlli, la successiva n-1 e così via, quindi si ha T(n)=n(n-1)/2 —> O(N²);
- Caso migliore: l’array è già ordinato e verrà effettuata una sola iterazione della sequenza;
SPAZIO DI ESECUZIONE
Lo spazio totale utilizzato dall’algoritmo è pari ad O(n), mentre quello ausiliario è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
SELECTION SORT
Il selection sort o ordinamento per selezione, opera dividendo la sequenza di input in due parti: la sottosequenza di elementi già ordinati (che occupa le prime posizioni dell’array) e la sottosequenza di elementi non ordinati (che occupa il resto dell’array).
Inizialmente, la sottosequenza ordinata è vuota, mentre quella non ordinata rappresenta l’intero input. L’algoritmo seleziona di volta in volta il numero minore nella sottosequenza non ordinata e lo sposta in quella ordinata.
public static void selectionSort(int[] arr) {
for (int i=0; i<arr.length-1; i++) {
int index = i;
for (int j=i+1; j<arr.length; j++)
if (arr[j] < arr[index])
index = j;
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
Il ciclo esterno si utilizza per tenere conto dell’i-esima posizione dell’array, mentre il secondo ciclo serve per trovare l’elemento più piccolo a partire dall’i-esima +1 posizione. Se viene trovato un elemento più piccolo di quello in posizione i, avviene lo scambio.
PROPRIETà
COMPLESSITÀ COMPUTAZIONALE
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione variabile, confronto ed incremento di un valore intero hanno un tempo di esecuzione pari ad O(1).
Dal punto di vista del numero di operazioni svolte dall’algoritmo, non esiste un caso favorevole o uno sfavorevole: qualunque sia la disposizione iniziale degli elementi della sequenza da ordinare, il numero di operazioni effettuate per ordinare la sequenza sarà pari ad O(N²).
Il ciclo esterno esegue n iterazioni, mentre quello interno esegue n-i iterazioni. Si ha quindi T(n)=n(n-1)/2 —> O(N²).
SPAZIO DI ESECUZIONE
Lo spazio totale utilizzato dall’algoritmo è pari ad O(n), mentre quello ausiliario è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
INSERTION SORT
L’insertion sort o ordinamento per inserimento è un algoritmo di ordinamento molto semplice, di complessità quadratica, ma solitamente più efficiente di algoritmi come il selection sort o il bubble sort. È molto efficiente per l’ordinamento di array di dimensione molto piccola o per array parzialmente ordinati.
L’idea di ordinamento è simile al modo in cui un giocatore di bridge ordina le carte nella propria mano. Si inizia con la mano vuota e le carte capovolte sul tavolo, poi si prende una carta alla volta dal tavolo e la si inserisce nella giusta posizione. Per trovare la giusta posizione per una carta, la si confronta con le altre carte nella mano, da destra verso sinistra. Ogni carta più grande verrà spostata verso destra in modo da fare posto alla carta da inserire.
public static void insertionSort(int[] arr){
for (int i=1; i <arr.length; i++)
for (int j=i; j>0 && arr[j]<arr[j-1]; j--)
if(arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
Si utilizzano due indici: uno punta all’elemento da ordinare e l’altro all’elemento immediatamente precedente. Se l’elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto, altrimenti il primo indice avanza. L’algoritmo prende in considerazione un singolo elemento alla volta e, ad ogni iterazione, fa crescere la porzione ordinata dell’array. Il tutto si ripete finché non restano elementi da prendere in considerazione. Grazie alla condizione arr[j]<arr[j-1] inserita nel ciclo più interno, si possono evitare delle iterazioni nel caso in cui gli elementi gli elementi successivi da analizzare siano già ordinati.
PROPRIETà
COMPLESSITÀ COMPUTAZIONALE
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione variabile, confronto ed incremento di un valore intero hanno un tempo di esecuzione pari ad O(1). Il tempo di esecuzione dell’algoritmo è dato dalla complessità del corpo dei cicli for annidati per il numero di volte in cui essi vengono eseguiti.
- Caso peggiore: l’array è ordinato in maniera inversa; ogni iterazione dovrà scorrere e spostare ciascun elemento della sottosequenza ordinata prima di poter inserire il primo elemento della sottosequenza non ordinata.
- Caso migliore: l’array è già ordinato ed in ogni iterazione il primo elemento della sottosequenza non ordinata viene confrontato solo con l’ultimo della sottosequenza ordinata;
SPAZIO DI ESECUZIONE
Lo spazio totale utilizzato dall’algoritmo è pari ad O(n), mentre quello ausiliario è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
SHELL SORT
L’Insertion Sort è efficiente per array parzialmente ordinati, ma inefficiente negli altri casi perché sposta gli elementi solo di una posizione per volta e spesso devono essere spostati più volte prima di arrivare nella posizione corretta.
L’idea sulla quale si basa lo Shell Sort è che gli elementi vengono spostati di diverse posizioni alla volta man mano che risistema i valori, diminuendo gradualmente la dimensione del passo sino ad arrivare ad 1. Alla fine lo Shell Sort eseguirà un Insertion Sort, ma i dati saranno già piuttosto ordinati e quindi il procedimento sarà efficiente.
public static void shellSort(int arr[]) {
int n = arr.length;
int h = 1;
while (h < n/3)
h = 3*h + 1;
while (h >= 1) {
for (int i=h; i<n; i++)
for (int j=i; j>=h && arr[j]<a[j-h]; j-=h){
int temp=arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
h /= 3;
}
Esistono diverse implementazioni dello Shell Sort, più o meno efficienti, ma in questo specifico caso si utilizza una sequenza di incremento nota come Formula di Sedgewick che decrementa il passo di un valore h.
Durante l’ordinamento dell’array, si inserisce ciascun elemento tra gli elementi precedenti della sottosequenza, scambiandolo con gli elementi con valore più alto (spostandoli a destra di una posizione nella sottosequenza). Per effettuare questa operazione si utilizza l’insertion Sort, ma modificato in modo che decrementi j di un valore h piuttosto che di 1 durante lo scorrimento dell’array.
Lo Shell Sort viene spesso utilizzato negli embedded system grazie al fatto che, richiedendo poco codice, non necessita di call stack risultando, di fatto, molto efficiente su questi dispositivi.
Inoltre, lo Shell Sort può essere utilizzato come sotto-algoritmo dell’Introsort, un principio di ordinamento utilizzato, ad esempio, nell’algoritmo di compressione bzip2.
PROPRIETà
COMPLESSITÀ COMPUTAZIONALE
TEMPO DI ESECUZIONE
Le operazioni di inizializzazione variabile, confronto ed incremento di un valore intero hanno un tempo di esecuzione pari ad O(1).
Le prestazioni dell’algoritmo dipendono non solo dal numero di incrementi, ma anche dalle interazioni aritmetiche tra gli incrementi come la dimensione dei loro comuni divisori ed altre proprietà. Sono state studiate numerose sequenze di incremento, ma probabilmente la migliore non è ancora stata trovata. La sequenza di Sedgewick utilizzata nell’algoritmo qui descritto è semplice da calcolare ed utilizzare ed ha delle prestazioni, nel caso peggiore, che sono superiori ad altre sequenze.
A differenza dell’Insertion Sort o del Selection Sort, lo Shell Sort è efficiente anche per grossi array.
Lo studio delle prestazioni di quest’algoritmo è complesso e richiede numerose dimostrazioni matematiche.
Il caso peggiore dello Shell Sort è l’Insertion Sort base (usando un passo h = 1), che richiede O(n²) confronti e scambi.
La complessità nel caso medio dipende sia dall’ordinamento già esistente sui dati in input, sia dalla sequenza di incremento utilizzata. Inoltre, come afferma Robert Sedgewick nel libro citato a fine articolo, non sono disponibili risultati matematici riguardo il numero di confronti nel caso medio per sequenze di input ordinate casualmente.
Con la sequenza di Sedgewick, l’algoritmo esegue O(n4/3) passi per ordinare una sequenza di lunghezza n nel caso migliore.
SPAZIO DI ESECUZIONE
Lo spazio totale utilizzato dall’algoritmo è pari ad O(n), mentre quello ausiliario è pari ad O(1) perché non vengono utilizzate strutture dati supplementari.
Spero che l’articolo sia stato di vostro gradimento e vi do appuntamento al prossimo!
BIBLIOGRAFIA
https://it.wikiversity.org/wiki/Il_problema_dell%27ordinamento
https://en.wikipedia.org/wiki/Bubble_sort
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Selection_sort
https://en.wikipedia.org/wiki/Shell_sort
Algorithms Fourth Edition di Robert Sedgewick e Kevin Wayne
