Algoritmo di ordinamento per selezione
Sia dato un elenco di elementi numerici. Il metodo di ordinamento basato sulla selezione è il seguente:
Trovare il valore minimo, spostarlo nella prima posizione di un nuovo elenco e marcare la posizione dell'elemento affinchè non venga nuovamente selezionato
Cercare il successivo elemento minimo, spostarlo nella seconda posizione dell'elenco e marcare la sua posizione per non selezionarlo più
continuare fino a quando si sono selezionati tutti gli elementi
In questo metodo gli elementi vengono duplicati in un secondo elenco.
Un miglioramento dell'algoritmo consiste nello spostare l'elemento selezionato nella sua posizione finale all'interno dello stesso elenco, scambiandolo con quello che occupa quella posizione, non considerando più quella posizione nelle successive selezioni.
Il modo più semplice per non prendere più in considerazione l'elemento collocato nella sua posizione finale consiste nello spostare gli elementi che devono occupare le posizioni estreme, cioè gli elementi massimi o gli elementi minimi.
Algoritmo di ordinamento per Selezione:
Ripetere le operazioni seguenti assegnando alla variabile k i valori da N-1 a 1, con decremento di k di 1
Ricercare il valore massimo tra gli elementi X[k], ..., X[0] annotando la sua posizione posMax
scambia gli elementi X[posMax] e X[k].
(a questo punto gli elementi tra k e N-1 sono ordinati)
Esempio:
Ad ogni passo del ciclo vengono mostrati
gli elementi nell'array X
su sfondo rosso la posizione indicata dalla variabile k
su sfondo verde la posizione indicata dallla variabile posMax
La variabile k, quindi, ha il significato di indicare la posizione in cui collocare il massimo e la variabile posMax di indicare la posizione in cui è stato individuato il massimo tra gli elementi che precedono il k-mo.
Passo 1:
Elementi nell'array X da ordinare:
| valori → | 7 | 54 | 15 | 4 | 8 |
| indice → | 0 | 1 | 2 | 3 | 4 |
Variabili:
k = 4
posMax = 1
Si scambiano gli elementi in posizione 4 e 1.
Passo 2:
Dopo lo scambio, gli elementi nell'array X si trovano nel seguente ordine:
| valori → | 7 | 8 | 15 | 4 | 54 |
| indice → | 0 | 1 | 2 | 3 | 4 |
Variabili:
k = 3
posMax = 2
Si scambiano gli elementi in posizione 3 e 2.
Passo 3:
Dopo lo scambio, gli elementi nell'array X si trovano nel seguente ordine:
| valori → | 7 | 8 | 4 | 15 | 54 |
| indice → | 0 | 1 | 2 | 3 | 4 |
Variabili:
k = 2
posMax = 1
Si scambiano gli elementi in posizione 2 e 1.
Passo 4:
Dopo lo scambio, gli elementi nell'array X si trovano nel seguente ordine::
| valori → | 7 | 4 | 8 | 15 | 54 |
| indice → | 0 | 1 | 2 | 3 | 4 |
Variabili:
k = 1
posMax = 0
Si scambiano gli elementi in posizione 1 e 0.
L'algoritmo termina. Gli elementi nell'array X sono ordinati:
| 4 | 7 | 8 | 15 | 54 |
| 0 | 1 | 2 | 3 | 4 |
Diagramma di Flusso:
La funzione massimo riceve come parametro l'indice dell'elemento fino al quale cercare il massimo e restituisce la posizione del massimo. 
fig. 3: Funzione di ricerca del Massimo | L'algoritmo di ordinamento per selezione, cerca il massimo e lo porta nelle ultime posizioni dell'array 
fig. 4: Ordinamento per selezione |
Algoritmo di ordinamento mediante conteggio
fig. 5: Ordinamento per conteggio
Dato un insieme di elementi ordinati, quello che occupa la posizione j è preceduto da (j - 1) elementi.
L'algoritmo di ordinamento mediante conteggio, quindi, si basa sulla semplice osservazione che per ogni elemento dell'insieme si devono contare quanti elementi lo precedono nell'elenco ordinato.
Si suppone che gli elementi siano: X[0], X[1], ..., X[N-1]
e che per ogni elemento ci sia un conteggio C[0], C[1], ..., C[N-1]
Al termine dell'algoritmo gli elementi dell'array C contengono un numero che rappresenta la quantità di elementi che precedono il corrispondente elemento nell'array X
I passi dell'algoritmo sono i seguenti:
Azzeramento dei contatori C[0], ..., C[N-1]
ripeti l'operazione seguente facendo assumere alla variabile I tutti i valori compresi tra N-1 e 1.
ripeti l'operazione seguente facendo assumere alla variabile J tutti i valori compresi tra I e 0.
se X[i] < X[j] incrementare C[j] di 1 altrimenti incrementare C[i] di 1
L'algoritmo lascia tutti gli elementi dove si trovano, non li rimette in ordine. Per ogni elemento si conosce quale dovrebbe essere la sua posizione nell'elenco ordinato.
Se si tenta di metterli al loro posto mediante questo algoritmo, bisogna tener presente che gli elementi uguali occupano la stessa posizione.
In altri termini questo algoritmo fornisce un'indicazione che si può paragonare a una sorta di posizione in classifica.
Ordinamento per Inserimento
fig. 6: Ordinamento per Inserimento
L'algoritmo di ordinamento mediante inserimento imita il comportamento di una persona che possiede delle schede numerate da riordinare.
Se una certa quantità di schede sono già state ordinate, per posizionare la prossima scheda si devono scandire le schede, dalla prima verso l'ultima, avanzando fintanto che si incontrano schede con numerazione inferiore, appena si incontra una scheda con numerazione maggiore di quella da inserire, si fa spazio per inserire la nuova scheda.
L'algoritmo consiste nei seguenti passi:
Ripetere le operazioni seguenti assegnando alla variabile J i valori da 1 a N.
La variabile J indica la posizione dell'elemento da inserire all'interno degli elementi precedenti, che si suppone siano già ordinati.Assegnare alla variabile i l'indice del massimo elemento già ordinato, cioè:
i ← J-1,
Assegnare alla variabile K il valore che si deve inserire tra quelli ordinati:
K ← X[J] (L'elemento X[J], essendo stato copiato nella variabile K verrà sovrascritto)ripetere:
Se il valore da inserire è minore dell'i-mo elemento
fare spazio per inserire l'elemento
(cioè copiare l'elemento in una posizione successiva:
X[i+1] ← X[i])
e prepararsi a confrontare l'elemento da inserire con l'elemento nella posizione precedente
(cioè i ← i - 1)fintanto che i ≥ 0
Inserire l'elemento nella posizione i+1
A questo punto si può arrivare da due direzioni diverse: Se i < 0, K è l'elemento più piccolo trovato, se invece i>0 l'elemento è maggiore di X[i], quindi va in posizione i+1
Esempio di ordinamento per inserimento
Passo 1:
Elementi nell'array X da ordinare:
| 7 | 54 | 15 | 4 | 8 |
| 0 | 1 | 2 | 3 | 4 |
Variabili:
l'elemento da inserire (X[1]) viene copiato in una variabile: k ← 54
si assume che l'elemento X[0] sia già al suo posto (se non lo è lo si sposta).
Risultando k > X[0] il valore k viene scritto nella posizione successiva, cioè in X[1]
Passo 2:
A questo punto si assume che gli elementi X[0] e X[1] siano ordinati.
| 7 | 54 |
| X[0] | X[1] |
Tra questi, si vuole trovare dove inserire l'elemento X[2]
l'elemento da inserire (X[2]) viene copiato in una variabile: k ← 15
Si procede a confrontare X[2] con X[1]. Risulta 15 < 54, quindi il valore 54 viene copiato dalla posizione 1 alla posizione 2:
| 7 | 54 | 54 |
| 0 | 1 | 2 |
Quindi si passa a confrontare l'elemento k con l'elemento X[0]. Risulta che 7 < 15, quindi il valore contenuto in k viene inserito dopo X[0]:
| 7 | 15 | 54 |
| 0 | 1 | 2 |
i restanti passi sono simili a quelli appena descritti.
Ordinamento in Lista
fig. 7: Ordinamento in Lista