Esercitazioni per il laboratorio di Informatica e Sistemi
* * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * * * * * * * *
Algoritmo di ordinamento per selezione
Sia dato un elenco di elementi numerici.
Il metodo di ordinamento basato sulla selezione è il seguente:
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 Selezione:
Esempio:
Ad ogni passo del ciclo vengono mostrati
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:
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:
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:
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::
Variabili:
k = 1 - posMax = 0
Si scambiano gli elementi in posizione 1 e 0.
L'algoritmo termina. Gli elementi nell'array X sono ordinati:
- 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
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 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:
| 7 | 54 | 15 | 4 | 8 |
| 0 | 1 | 2 | 3 | 4 |
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:
| 7 | 8 | 15 | 4 | 54 |
| 0 | 1 | 2 | 3 | 4 |
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:
| 7 | 8 | 4 | 15 | 54 |
| 0 | 1 | 2 | 3 | 4 |
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::
| 7 | 4 | 8 | 15 | 54 |
| 0 | 1 | 2 | 3 | 4 |
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 |
La funzione massimo riceve come parametro l'indice dell'ultimo 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
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
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'ordinamento che si desidera.
Si suppone che gli elementi sono X[0], X[1], ..., X[N-1]
e che per ogni elemento ci sia un contatore 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:
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.
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'ordinamento che si desidera.
Si suppone che gli elementi sono X[0], X[1], ..., X[N-1]
e che per ogni elemento ci sia un contatore 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
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
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:
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 ci si arriva 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
Esempio:
Passo 1:
Elementi nell'array X da ordinare:
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.
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 spostato dalla posizione 1 alla posizione 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]:
passo 3:
Esempio:
Passo 1:
Elementi nell'array X da ordinare:
| 7 | 54 | 15 | 4 | 8 |
| 0 | 1 | 2 | 3 | 4 |
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 spostato dalla posizione 1 alla posizione 2:
| 7 | 54 | 54 |
| 0 | 1 | 2 |
| 7 | 15 | 54 |
| 0 | 1 | 2 |
passo 3:
Ordinamento in Lista
fig. 7: Ordinamento in Lista
fig. 7: Ordinamento in Lista