Il Merge Sort,  inventato da John Von Neumann nel 1945, è molto simile al Quick Sort, ma  l’elemento pivot, in questo caso, viene scelto sempre nel centro.

L’idea principale è che, avendo due array ordinati, è molto semplice fonderli in un unico array ordinato. Inoltre,  un’array di un elemento  è sempre ordinato.

Unendo questi concetti,  si ha un algoritmo che, dopo aver suddiviso ricorsivamente l’array iniziale A in n sotto-array, costituiti da un solo elemento,  fonde i sotto-array e fino a ottenere  un’unico array ordinato.

Codificando il tutto si ha:

L’algoritmo è diviso in due metodi: il MergeSort e il Merge.

Il MergeSort riceve in input l’array A e i due indici p e r, che permettono di identificare l’elemento a_p e l’elemento a_r, ossia il primo e l’ultimo elemento.

Esso divide, ricorsivamente,  l’array in due parti, in modo tale che i due sotto-array ottenuti abbiano un ugual numero di elementi (a meno di uno, nel caso di insiemi con cardinalità dispari). Durante la suddivisione l’array non viene modificato.

La riga 2 del codice individua l’indice q dell’elemento che si trova a metà dell’array.

Dopodiché, viene chiamato ricorsivamente il metodo MergeSort sulla prima metà e sulla seconda metà.

La procedura si ripete ricorsivamente fino a quando si arriva ad array composti da un solo elemento, ossia  quando p = r .

A questo punto, entra in gioco la procedura Merge, che provvede alla “fusione” dei due array  A₀ = {ap ,ap+1,…,aq } e A ₀₀ = {aq+1,aq+2,…,ar }.

La fusione avviene scansionando in parallelo entrambe le sequenze (ciclo principale, righe 2–8), e copiando nell’insieme di appoggio B l’elemento minore tra ai e aj.

Nel caso in cui una delle due sequenze è stata copiata completamente in B, la procedura prosegue copiando in B gli elementi rimanenti dell’altra sotto-sequenza. Infine gli elementi ordinati dell’insieme B vengono copiati nuovamente in A, ottenendo alla fine l’ordinamento di A.

Esempio

La complessità computazionale del Merge Sort è sempre O(n log2 n), a prescindere dai dati in input,  quindi ha la più bassa complessità degli algoritmi visti fino ad ora.

Gli svantaggi sono che necessita di un vettore di appoggio ed effettua spostamenti anche nel caso in cui  il vettore di partenza è già ordinato

L’algoritmo Quick Sort, ideato da Charles Antony Richard Hoare nel 1960, è forse il più famoso algoritmo di ordinamento, ed ha, nel caso medio, le migliori prestazioni tra gli algoritmi basati su confronto. 

Adotta una strategia di tipo divide et impera, ossia divide il problema in tanti sotto problemi, fino a raggiungere dei sotto problemi facilmente risolvibili.

Questo approccio è conveniente solo se lo sforzo per ricomporre le soluzioni dei sotto problemi ed ottenere la soluzione del problema iniziale, è inferiore allo sforzo per risolvere il problema nella sua interezza.

In termini più tecnici abbiamo:

1. Scelta di un elemento dell’array, detto “pivot”
2. Suddivisione del vettore in due “sub-array”
3. Nel primo array tutti gli elementi minori o uguali al pivot, nel secondo quelli maggiori
4. Ordinare i due sub-array separatamente, ossia applicare ricorsivamente per ognuno i passi dal 1 al 4
5. Fondere i due sub-array ordinati insieme.

Riassumendo, abbiamo che l’ordinamento avviene mediante un algoritmo ricorsivo, che viene applicato a sotto-array sempre più piccoli, fino ad arrivare a sotto-array di pochi elementi, che possono essere risolte direttamente, senza altre chiamate ricorsive.

Codificando il tutto si ha:

Procedure Quicksort(A)
Input A, vettore a1, a2, a3 .. an
  begin
    if n ≤ 1 then return A
    else
      begin
        scegli un elemento pivot ak
        calcola il vettore A1 dagli elementi ai di A tali che i ≠ K e ai ≤ ak
        calcola il vettore A2 dagli elementi aj di A tali che j ≠ K e aj > ak
        A1 ← Quicksort(A1)
        A2 ← Quicksort(A2)
        return A1 · (ak) · A2;
      end

Esempio

Per semplicità di esposizione, è stato scelto come pivot sempre l’elemento centrale.

Rimane da specificare come scegliere il pivot.

E’ stato dimostrato che scegliendo in modo random il pivot, il Quick Sort ha una complessità media di O(n*log n) ma nel caso peggiore di O(n²).

L’ideale sarebbe però che tale risultato fosse raggiunto sempre: a ciò provvede il Merge Sort.

L’algoritmo di ordinamento InsertSort (ordinamento diretto) nasce dal concetto che per ordinare un array ordinato è sufficiente costruirne uno nuovo ordinato, inserendo gli elementi al posto giusto da subito. Nella pratica, non è necessario crearne uno nuovo ma dividere quello esistente in due parti, una ordinata e l’altra no.

Esempio:

Vogliamo ordinare l’insieme A = {5, 3, 2, 1, 4}.

Iterazione 1. A = {5 | 2, 3, 1, 4} → A = {2, 5 | 3, 1, 4}

Iterazione 2. A = {2, 5 | 3, 1, 4} → A = {2,3, 5 | 1, 4}

Iterazione 3. A = {2, 3, 5 | 1, 4} → A = {1, 2, 3, 5 | 4}

Iterazione 4. A = {1, 2, 3, 5 | 4} → A = {1, 2, 3,4, 5}

Codificando l’Insert Sort abbiamo:

1: per i = 2, 3,...,n ripeti 
	2: k = i −1 
	3: fintanto che k ≥ 1 e ak > ak+1 ripeti 
		4: scambia ak e ak+1 
		5: k = k −1 
	6: fine-ciclo 
7: fine-ciclo 

Nel caso migliore, ossia quando l’array ègia ordinato, il numero di operazioni svolte dall’algoritmo è dell’ordine di n.

Nel caso peggiore, il numero di operazioni eseguite dall’algoritmo è:

La complessità dell’algoritmo nel caso peggiore è quindi O(n ² ).

L’algoritmo Bubble Sort  è basato sullo scambio di elementi adiacenti. Ogni coppia di elementi adiacenti viene comparata e invertita di posizione, se il primo è più grande del secondo. Quando questa operazione è stata ripetuta  per tutti gli elementi, si ha che l’elemento  più grande si trova in fondo, a destra, della sequenza considerata.

Dopodiché, si ripete questa procedura sugli elementi rimanenti, togliendo elemento più grande trovato prima.

L’algoritmo, iterando più volte  questi passaggi, fino a quando non ci saranno scambi. Allora l’array ottenuto sarà ordinato.

Deve il suo nome al modo in cui gli elementi vengono ordinati ossia quelli più piccoli “emergono” verso un’estremità della lista, così come fanno le bolle gassose in un bicchiere di acqua minerale; al contrario quelli più grandi “sprofondano” verso l’estremità opposta della sequenza.

Esempio

Abbiamo un array A = {3,5, 2, 4, 1} su cui applichiamo il bubble sort:

1. A = {3,5, 2, 4, 1} → A = {3,5,2, 4, 1} → A = {3, 2,5,4, 1} → A = {3, 2, 4,5,1} → A = {3, 2, 4, 1 | 5}

2. A = {3,2, 4, 1 | 5} → A = {2,3,4, 1 | 5} → A = {2, 3,4,1 | 5} → A = {2, 3, 1 | 4, 5}

3. A = {2,3, 1, | 4, 5} → A = {2,3,1 | 4, 5} → A = {2, 1 | 3, 4, 5}

4. A = {2,1 | 3, 4, 5} → A = {1, 2, 3, 4, 5}

Notare che, alla fine di ogni iterazione, l’elemento più grande del sottoinsieme ancora da ordinare, finisce in fondo alla sequenza, nella sua posizione definitivamente corretta, mentre la sottosequenza ancora in disordine si riduce di volta in volta di un elemento.

Codificando il Bubble Sort si ha:

1: flag = 1 
2: stop = n −1 
3: fintanto che flag = 1 ripeti
	 4: flag = 0 
	 5: per i = 1, 2,...,stop  ripeti 
		6: se ai > ai+1 allora 
			7: scambia ai e ai+1 
			8: flag = 1 
		9: fine-condizione 
	10: fine-ciclo 
	11: stop = stop −1 
12: fine-ciclo 

In Java si ha:

		int[] v = { 2, 4, 7, 3, 5 };
		boolean scambiFatti= false;
		for (int i = v.length - 1; i > 0; i--) {
			for (int j = 0; j <i; j++) {
				
				if (v[j] > v[j + 1])// inverti
				{
					int tmp = v[j];
					v[j] = v[j + 1];
					v[j + 1] = tmp;
					scambiFatti = true;
				}
				
			}
			
			if(!scambiFatti) {
				break;
			}
		}

		for (int i = 0; i < v.length; i++)
			System.out.println(v[i]);

Notare che il Bubble Sort corregge il difetto principale del selection sort, ossia il non accorgersi se l’array, a un certo punto, è già ordinato.

Anche in questo caso abbiamo due cicli annidati, ma, stavolta, l’algoritmo usa la variabile flag per terminare l’esecuzione, nel caso in cui l’insieme risulti ordinato.

Nel caso migliore, ossia quando l’insieme è già ordinato, l’algoritmo esegue un’unica scansione, quindi il numero di operazioni eseguite sarà dell’ordine di n.

Nel caso peggiore, alla prima iterazione vengono eseguite dunque sono necessarie n − 1 iterazioni del ciclo esterno per ordinare l’intera sequenza. Alla seconda n-2, e cosi via. Quindi il numero di operazioni svolte è:

Concludendo la complessità computazionale del Bubble Sort è di O(n ² ).

L’algoritmo Selection Sort è quello più semplice, quello che seguirebbe istintivamente qualsiasi persona. Da un gruppo da ordinare seleziona il più piccolo, lo toglie,  e lo inserisce nella giusta posizione in un gruppo ordinato.

In termini un po’ più tecnici, l’algoritmo ripete per n volte una procedura in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di scambiarlo con l’elemento che in quel momento occupa la posizione i. 

Ossia, alla prima iterazione verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione; alla seconda iterazione sarà selezionato il secondo elemento più piccolo dell’insieme ridotto (cioè costituito dagli elementi {a2,a3,…,an} ) e sarà scambiato con l’elemento che occupa la seconda posizione, e così via fino ad aver collocato nella posizione corretta tutti gli n elementi.

Considerando un vettore di n elementi l’algoritmo può essere codificato nel seguente modo :

per i = 1, 2,...,n ripeti
	per j = i +1,...,n ripeti
		se aj < ai allora
			scambia ai e aj
		fine-condizione
	fine-ciclo
fine-ciclo

In java diventa:

 		public void selectionSort(int [] array) {

	        for(int i = 0; i < array.length-1; i++) {
	            int minimo = i; //Partiamo dall' i-esimo elemento
	            for(int j = i+1; j < array.length; j++) {

	            //Qui avviene la selezione, ogni volta
	            //che nell' iterazione troviamo un elemento piú piccolo di minimo
	            //facciamo puntare minimo all' elemento trovato
	                    if(array[minimo]>array[j]) {
	                        minimo = j;
	                    }
	            }

	            //Se minimo e diverso dall' elemento di partenza
	            //allora avviene lo scambio
	            if(minimo!=i) { 
	                int k = array[minimo];
	                array[minimo]= array[i];
	                array[i] = k;
	            }
	        }
	    }

Esempio

Supponiamo di applicare il selection sort al seguente array

A = {4, 2, 1, 3}

Ad ognuno dei passi dell’algoritmo, viene selezionato l’elemento più piccolo nella porzione di insieme ancora da ordinare, scambiandolo con l’elemento che si trova nella prima posizione di tale sottoinsieme.

i = 1 A = (4, 2,1, 3) → A = (1 | 2, 4, 3)

i = 2 A = (1 | 2, 4, 3) → A = (1, 2 | 4, 3)

i = 3 A = (1, 2, | 4,3) → A = (1, 2, 3 | 4)

i = 4 A = (1, 2, 3 | 4) → A = (1, 2, 3, 4)

Dopo 4 iterazioni, l’array sarà ordinato.

Per misurare le prestazioni dell’algoritmo (anche detta complessità) conteremo il numero di confronti.

Alla prima ripetizione del ciclo esterno vengono compiute n −1 operazioni con il ciclo interno; alla seconda ripetizione del ciclo esterno vengono eseguite n−2 operazioni con il ciclo interno, e così via fino a quando i = n.

Il numero di confronti totali sarà:

(N-1) + (N-2) + (N-3) + … + 2 + 1 = N*(N-1)/2 = O(N²)

Da notare che l’algoritmo fa gli stessi confronti sia per un array disordinato, sia per un array già ordinato, ossia per il selection sort non esiste un caso migliore o peggiore ma fa sempre tutti i confronti.

Viene usato quando l’insieme da ordinare è composto da pochi elementi e quindi, anche se non è molto efficiente, ha il vantaggio di non essere troppo difficile da implementare.