Algoritmo di ordinamento per selezione

Algoritmo di ordinamento per selezione

L'algoritmo di ordinamento per selezione (di massimo o di minimo) è un algoritmo che opera in place. Infatti, l'array da ordinare, che possiamo chiamare “a”, è sia un dato di input che di output.

Idea incrementale

Applichiamo ora una variante dell'idea incrementale per l'ordinamento. L'algoritmo di ordinamento per inserimento è l'algoritmo basato sull'idea incrementale pura. L'idea questa volta è quella di costruire in modo incrementale l'array ordinato finale nel senso che, mediante un procedimento iterativo, viene costruito ad ogni passo una porzione dell'array finale ordinato. Tale porzione è da considerarsi definitiva ovvero gli elementi di tale porzione non verranno modificati nelle successive iterazioni.

Supponendo di essere arrivati al generico passo “i” del processo iterativo si ha che l'array può essere visto come diviso in due porzioni disgiunte (una definitivamente ordinata ed una ancora disordinata). L'idea è quella che ad ogni iterazione consente, partendo dalla situazione appena descritta, di aggiungere un elemento alla parte ordinata diminuendo di un elemento la parte disordinata: in questo modo, dopo n-1 iterazioni risulta essere ordinato.

Dinamica dell'algoritmo di ordinamento per selezione di minimo

Descriviamo ora la dinamica di un algoritmo di ordinamento per selezione di minimo. L'algoritmo considera porzioni dell'array di size via via decrescenti. Ogni porzione è la parte che abbiamo chiamato “parte disordinata dell'array”, la parte ordinata invece, è costituita dalla porzione complementare alla prima. Alla prima iterazione si considera la porzione massima dell'array, ovvero l'array stesso (infatti l'array stesso è disordinato).

Come già fatto a proposito dell'algoritmo di ordinamento per inserimento definiamo un indice di inizio (“i”) della porzione ed uno che ne fissa la fine. Poiché le porzioni considerate termineranno sempre con l'ultimo elemento dell'array, l'indice di fine porzione varrà sempre n (il size dell'array). L'aspetto centrale dell'algoritmo di ordinamento per selezione di minimo è la modalità con la quale si aggiunge un elemento alla porzione ordinata definitiva dell'array.

La modalità è la seguente: si calcola l'elemento minimo della porzione disordinata 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 porzione ordinata.