Algoritmo di ordinamento per selezione

Algoritmo di ordinamento per selezione di minimo

Sotto esame (al generico passo "i" tale porzione sarà quella definita nell'intervallo i-n) e si scambia l'elemento minimo trovato con quello che si trova al primo posto della stessa parte disordinata.

Al primo passo naturalmente non è ancora stata definita alcuna parte ordinata e la parte disordinata coincide con l'intero array. Va dunque ricercato l'elemento minimo dell'intero array e messo al primo posto di quest'ultimo: la porzione ordinata ora esiste ed ha size 1, mentre quella disordinata ha size n-1.

Volendo generalizzare in forma schematica e adoperando un linguaggio di pseudocodifica, le conclusioni fatte a proposito di questa modalità di ordinamento possono essere così riassunte:

Siamo ora in grado di descrivere la struttura generale dell'algoritmo di ordinamento per selezione di minimo.

L'algoritmo sarà costituito da due cicli innestati: un ciclo for esterno in cui la variabile di ciclo varia da 1 ad...

n-1 (gli n-1 passi del procedimento iterativo di ordinamento) ed un ciclo for interno la cui finalità è quello di calcolare l'elemento minimo della porzione in esame. Poiché ad ogni passo viene selezionato l'elemento minimo l'algoritmo prende il nome di algoritmo di ordinamento per selezione di minimo (selection sort). Avendo fatto tutte le considerazioni del caso in merito all'algoritmo di ordinamento per selezione di minimo è possibile definirne una prima versione nel linguaggio di pseudocodifica che già conosciamo:

La versione nella slide è scritta per un array di caratteri. Si noti che non è necessario conoscere il valore dell'elemento minimo quanto piuttosto la sua posizione (indicata in questo esempio con la variabile "indice_min"). L'elemento di "a" il cui indice è "indice_min" dev'essere scambiato con l'elemento di "a" il cui indice sarà

quello che determina l'inizio della porzione.Il for interno parte da k+1 in virtù dell'inizializzazione che assegna ad "indice_min" il valore "i" vengono coinvolti nei confronti per la determinazione del minimo dellaporzione 1-n tutti gli elementi a partire dall'i+1-esimo in poi.Il for interno è semplicemente un ciclo determinante l'elemento minimo dellaporzione di array sotto esame.Al termine del for interno viene effettuato lo scambio, attraverso un'appositafunction, tra l'i-esimo elemento (elemento di inizio della porzione disordinata) el'elemento il cui indice è il valore di "indice_min".Per effetto della chiamata alla function "scambiare_c" il minimo elemento vieneinserito al primo posto della porzione disordinata corrispondente; in questo modo laporzione ordinata viene incrementata di un elemento e la porzione disordinatadecrementata di 1.Analizziamo la complessità

dell'algoritmo.La complessità di spazio è "n" poiché l'algoritmo opera in place.Il corpo del for esterno viene eseguito n-1 volte. Il for interno viene eseguito per k che va da i+1 a n.L'operazione dominante è il confronto tra due elementi dell'array che si trova nell'if del for interno.Contando esplicitamente il numero di volte che viene valutato il predicato dell'if in questione si giunge alla conclusione in figura (si noti che per ogni iterazione viene effettuato, necessariamente, almeno un confronto).Ancora una volta la complessità di tempo dell'algoritmo è data dalla somma dei primi n numeri naturali che sappiamo essere esprimibile dalla formula di Gauss relativa.Il risultato a cui siamo pervenuti nel calcolo della complessità di tempo dell'algoritmo di ordinamento per selezione di minimo è una complessità assoluta e non una relativa al già discusso, "caso"

Il limite di quest'algoritmo consiste nel fatto che se l'array è già ordinato la complessità di tempo rimane invariata. In altri termini, l'algoritmo non è in grado di "accorgersi" del fatto che l'array dato in input sia già ordinato.

Algoritmo di ordinamento per selezione di massimo

L'idea dell'algoritmo di ordinamento per selezione di minimo può essere estesa dando luogo ad un altro algoritmo che prende il nome di algoritmo di ordinamento per selezione di massimo. Alla generica i-esima iterazione l'array risulta diviso in due porzioni di cui, questa volta, quella a sinistra è la porzione che abbiamo chiamato "disordinata" e quella a destra invece, quella ordinata. Al solito ogni iterazione ha lo scopo di aumentare il size della porzione ordinata e di diminuire invece, quello della porzione disordinata.