Esercizi · Algoritmi di ordinamento

Esercizi · Capitolo 3 · ogni soluzione si apre con un clic · Capitolo 3: Algoritmi di ordinamento · Eserciziario, volume 1 (PDF)

Gli esercizi di questo capitolo usano i tre algoritmi del capitolo «Algoritmi di ordinamento» (Insertion Sort, Exchange Sort e Selection Sort) nella loro versione in pseudocodice, con array indicizzati a partire da \(1\). In tutte le soluzioni valgono le seguenti convenzioni.

• In una tabella di traccia, ogni riga mostra lo stato dell'array dopo l'operazione descritta nell'ultima colonna. La chiave corrente di Insertion Sort è evidenziata in rosso; le celle modificate da uno spostamento, da un inserimento o da uno scambio sono evidenziate in blu.

• Un confronto tra chiavi è la valutazione di un confronto tra due chiavi: \(a[j] > \mathit{key}\) in Insertion Sort (valutato solo quando \(j \ge 1\)), \(a[i] > a[j]\) in Exchange Sort, \(a[j] < a[\mathit{minIdx}]\) in Selection Sort.

• Un passo è l'esecuzione di una riga dello pseudocodice; la valutazione della condizione di un ciclo while conta come un passo ogni volta che viene valutata, compresa l'ultima, quella che termina il ciclo.

• Per ogni \(n \in \Z_{\ge 1}\):

  \[ \sum_{k=1}^{n-1} k = 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}. \]

Esercizio 3.1: Algoritmi di ordinamento (E1)

Consideriamo gli array

\[ a=[3,1,2] \qquad \text{e} \qquad b=[2,1,2] \]

e i riarrangiamenti di un array, come nella definizione del problema dell'ordinamento.

Domande

1. Elencare tutti i riarrangiamenti di \(a\) e di \(b\). Quali di essi sono ordinati in ordine non decrescente?

2. Spiegare perché l'output del problema dell'ordinamento non è un array qualunque ordinato in ordine non decrescente: fornire un esempio di array ordinato in ordine non decrescente che non è un output corretto per \(a\).

3. Quanti riarrangiamenti ha un array di \(n\) elementi distinti? Calcolare il numero per \(n=5\), \(n=10\) e \(n=20\).

4. Consideriamo l'algoritmo BruteForceSort che genera uno a uno i riarrangiamenti dell'array e si ferma quando ne trova uno ordinato. Quanti riarrangiamenti può esaminare nel caso peggiore per un array di \(n\) elementi distinti? Confrontare con i \(\frac{n(n-1)}{2}\) spostamenti eseguiti nel caso peggiore da Insertion Sort.

Soluzione

1. L'array \(a=[3,1,2]\) ha \(3!=6\) riarrangiamenti:

   \[ [1,2,3],\ [1,3,2],\ [2,1,3],\ [2,3,1],\ [3,1,2],\ [3,2,1]. \]

   Solo \([1,2,3]\) è ordinato in ordine non decrescente.

   L'array \(b=[2,1,2]\) contiene due volte il valore \(2\), quindi scambiare i due \(2\) dà lo stesso array. I suoi riarrangiamenti distinti sono soltanto \(3\):

   \[ [1,2,2],\ [2,1,2],\ [2,2,1], \]

   e solo \([1,2,2]\) è ordinato. In entrambi i casi il riarrangiamento ordinato è unico: l'output del problema dell'ordinamento è univocamente determinato dall'input.

2. L'output deve essere un riarrangiamento dell'input ordinato. Ad esempio, gli array \([1,1,1]\) e \([1,2,4]\) sono ordinati, ma non sono un output corretto per \(a=[3,1,2]\), perché non contengono gli stessi elementi. Un “algoritmo” che sovrascrive tutte le componenti con \(0\) produce un array ordinato, ma non risolve il problema dell'ordinamento. Per questo, quando si dimostra che un algoritmo di ordinamento è corretto, bisogna mostrare anche che l'array finale contiene gli elementi originali.

3. Un array di \(n\) elementi distinti ha

   \[ n!=n\cdot(n-1)\cdots 2\cdot 1 \]

   riarrangiamenti: ci sono \(n\) scelte per la prima posizione, \(n-1\) per la seconda, e così via. Quindi

   \[ 5!=120,\qquad 10!=3\,628\,800,\qquad 20!=2\,432\,902\,008\,176\,640\,000\approx 2.4\cdot 10^{18}. \]

4. Nel caso peggiore il riarrangiamento ordinato è l'ultimo generato, quindi BruteForceSort può esaminare tutti gli \(n!\) riarrangiamenti (e verificare ciascuno di essi richiede fino a \(n-1\) confronti). Insertion Sort esegue al più \(\frac{n(n-1)}{2}\) spostamenti:

   \(n\)	\(n!\)	\(\frac{n(n-1)}{2}\)
   5	120	10
   10	3 628 800	45
   20	2 432 902 008 176 640 000	190

   Poiché \(n!\ge 2^{n-1}\) per ogni \(n\ge 1\), il numero di riarrangiamenti esaminati dall'approccio a forza bruta cresce almeno in modo esponenziale con \(n\), mentre il numero di spostamenti di Insertion Sort cresce solo in modo quadratico. Già per \(n=20\), anche esaminando \(10^9\) riarrangiamenti al secondo, BruteForceSort potrebbe impiegare

   \[ \frac{2.43\cdot 10^{18}}{10^{9}} \text{ s} \approx 2.43\cdot 10^{9} \text{ s} \approx 77 \text{ anni}. \]

Esercizio 3.2: Algoritmi di ordinamento (E2)

Consideriamo il problema di verificare se un array \(a[1..n]\) di \(n\ge 1\) numeri naturali è ordinato in ordine non decrescente, e il seguente algoritmo.

Algoritmo: IsSorted

Input: Un array \(a[1..n]\) di \(n\) numeri naturali

Output: true se \(a[1]\le a[2]\le\cdots\le a[n]\), false altrimenti

1function IsSorted(a, n)

2\(i := 1\)

3while \(i \le n-1\) do

4if \(a[i] > a[i+1]\) then

5return false

6end

7\(i \leftarrow i + 1\)

8end

9return true

10end

Domande

1. Applicare IsSorted agli array \([1,3,3,7,9]\), \([2,5,4,8]\), \([9,1,2,3]\) e \([1]\). Per ciascun array indicare l'output e il numero di passi eseguiti.

2. IsSorted è un algoritmo basato su confronti? Quanti confronti tra chiavi esegue nel caso peggiore?

3. Sia \(S(n)\) il numero di passi eseguiti da IsSorted nel caso peggiore, per un array di \(n\) elementi. Calcolare \(S(n)\) e confrontare il numero di confronti tra chiavi di IsSorted con il numero di confronti tra chiavi nel caso peggiore degli algoritmi di ordinamento del capitolo.

4. Dimostrare che IsSorted restituisce true se e solo se l'array \(a[1..n]\) è ordinato in ordine non decrescente.

Soluzione

1. Executions:

   • \([1,3,3,7,9]\) (\(n=5\)): i confronti \(1\le 3\), \(3\le 3\), \(3\le 7\), \(7\le 9\) sono tutti soddisfatti; il ciclo termina quando \(i=5\) e l'output è true. Passi: riga 2 una volta, riga 3 \(5\) volte, righe 4 e 7 \(4\) volte ciascuna, riga 9 una volta:

     \[ 1+5+4+4+1=15. \]

   • \([2,5,4,8]\) (\(n=4\)): \(a[1]=2\le 5\); poi \(a[2]=5>a[3]=4\), quindi l'output è false per \(i=2\). Passi: riga 2 una volta, riga 3 due volte, riga 4 due volte, riga 7 una volta, riga 5 una volta:

     \[ 1+2+2+1+1=7. \]

   • \([9,1,2,3]\) (\(n=4\)): \(a[1]=9>a[2]=1\), quindi l'output è false per \(i=1\). Passi: le righe 2, 3, 4, 5 una volta ciascuna:

     \[ 1+1+1+1=4. \]

   • \([1]\) (\(n=1\)): la condizione \(1\le 0\) è falsa e l'output è true. Passi: le righe 2, 3, 9 una volta ciascuna:

     \[ 1+1+1=3. \]

2. Sì: l'algoritmo accede alle chiavi soltanto per confrontarne due (riga 4); non le modifica mai e non esegue mai operazioni aritmetiche su di esse. Nel caso peggiore esegue \(n-1\) confronti tra chiavi, uno per ogni coppia di posizioni consecutive.

3. Il caso peggiore è quello in cui l'algoritmo non ritorna mai alla riga 5, cioè quando l'array è ordinato. Il numero di volte in cui ciascuna riga viene eseguita è:

   • la riga 2 viene eseguita \(1\) volta;

   • la riga 3 viene eseguita \(n\) volte;

   • la riga 4 viene eseguita \(n-1\) volte;

   • la riga 5 non viene eseguita;

   • la riga 7 viene eseguita \(n-1\) volte;

   • la riga 9 viene eseguita \(1\) volta.

   Quindi

   \[ S(n)=1+n+(n-1)+(n-1)+1=3n, \]

   in accordo con il punto 1 (\(15=3\cdot 5\) per l'array ordinato di \(5\) elementi, \(3=3\cdot 1\) per \(n=1\)).

   Verificare se un array è ordinato richiede al più \(n-1\) confronti tra chiavi, un numero che cresce linearmente con \(n\), mentre Insertion Sort, Exchange Sort e Selection Sort eseguono \(\frac{n(n-1)}{2}\) confronti tra chiavi nel caso peggiore, un numero che cresce quadraticamente con \(n\). Per \(n=100\): \(99\) confronti contro \(4\,950\).

4. L'algoritmo restituisce false soltanto alla riga 5, e soltanto dopo aver trovato un indice \(i\) con \(a[i] > a[i+1]\): in questo caso l'array non è ordinato, perché due elementi consecutivi sono nell'ordine sbagliato. Quindi, se l'array è ordinato, l'algoritmo non restituisce mai false; poiché \(i\) aumenta di \(1\) a ogni iterazione, il ciclo termina dopo \(n-1\) iterazioni e l'algoritmo restituisce true alla riga 9.

   Viceversa, se l'algoritmo restituisce true, il ciclo è stato completato, quindi il confronto alla riga 4 era falso per ogni \(i \in \{1, 2, \dots, n-1\}\):

   \[ a[1] \le a[2], \quad a[2] \le a[3], \quad \dots, \quad a[n-1] \le a[n]. \]

   Concatenando queste disuguaglianze, \(a[1] \le a[2] \le \dots \le a[n]\): l'array è ordinato. Dunque IsSorted restituisce true se e solo se l'array è ordinato in ordine non decrescente.

Esercizio 3.3: Algoritmi di ordinamento (E3)

Consideriamo l'array di record \((\mathit{key},\ \mathit{label})\), in cui si confrontano solo le chiavi,

\[ a=[(3,A),\ (1,B),\ (3,C),\ (2,D),\ (1,E)], \]

e gli algoritmi Insertion Sort e Selection Sort del capitolo (Insertion Sort sposta \(a[j]\) a destra finché \(a[j]>\mathit{key}\); Selection Sort scambia \(a[i]\) con il minimo di \(a[i..n]\), scegliendo il primo minimo trovato).

Domande

1. Applicare Insertion Sort ad \(a\), mostrando l'array dopo ogni iterazione del ciclo esterno. Il risultato è stabile?

2. Applicare Selection Sort ad \(a\), mostrando l'array dopo ogni iterazione del ciclo esterno. Il risultato è stabile?

3. Uno studente sostituisce la condizione \(a[j]>\mathit{key}\) di Insertion Sort con \(a[j]\ge \mathit{key}\). Il nuovo algoritmo è ancora corretto? È stabile?

4. Insertion Sort e Selection Sort sono in-place? Descrivere un metodo di ordinamento che non è in-place.

Soluzione

1. Insertion Sort (la chiave inserita è evidenziata in rosso):

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)
   iniziale	\((3,A)\)	\((1,B)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
   2	\((1,B)\)	\((3,A)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
   3	\((1,B)\)	\((3,A)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
   4	\((1,B)\)	\((2,D)\)	\((3,A)\)	\((3,C)\)	\((1,E)\)
   5	\((1,B)\)	\((1,E)\)	\((2,D)\)	\((3,A)\)	\((3,C)\)

   Per \(i=3\), \(a[2]=(3,A)\) non è \(>3\), quindi \((3,C)\) resta dopo \((3,A)\); per \(i=5\), gli spostamenti si fermano in \((1,B)\), perché \(1>1\) è falso. Nell'output \(B\) precede \(E\) e \(A\) precede \(C\), come nell'input: il risultato è stabile. In generale, Insertion Sort è stabile, perché una chiave non viene mai spostata prima di una chiave uguale (la condizione di spostamento è una disuguaglianza stretta).

2. Selection Sort (le due posizioni scambiate sono evidenziate in blu):

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(\mathit{minIdx}\)
   iniziale	\((3,A)\)	\((1,B)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)
   1	\((1,B)\)	\((3,A)\)	\((3,C)\)	\((2,D)\)	\((1,E)\)	2
   2	\((1,B)\)	\((1,E)\)	\((3,C)\)	\((2,D)\)	\((3,A)\)	5
   3	\((1,B)\)	\((1,E)\)	\((2,D)\)	\((3,C)\)	\((3,A)\)	4
   4	\((1,B)\)	\((1,E)\)	\((2,D)\)	\((3,C)\)	\((3,A)\)	4 (nessuno scambio)

   Le chiavi sono ordinate, ma \((3,C)\) precede \((3,A)\), mentre nell'input \(A\) precedeva \(C\): il risultato non è stabile. Lo scambio per \(i=2\) ha spostato \((3,A)\) dalla posizione \(2\) alla posizione \(5\), “saltando” \((3,C)\). Quindi Selection Sort non è stabile (un controesempio ancora più piccolo è \([(2,A),(2,B),(1,C)]\), che diventa \([(1,C),(2,B),(2,A)]\)).

3. Con \(a[j]\ge \mathit{key}\) l'algoritmo è ancora corretto: le chiavi sono ancora ordinate, perché \(\mathit{key}\) viene inserita dopo tutti gli elementi \(<\mathit{key}\) e prima di tutti gli elementi \(\ge \mathit{key}\). Tuttavia non è stabile, perché \(\mathit{key}\) viene spostata prima delle chiavi uguali. Su \(a\):

   \[ [(3,A),(1,B),(3,C),(2,D),(1,E)]\ \longrightarrow\ [(1,E),(1,B),(2,D),(3,C),(3,A)], \]

   dove entrambe le coppie di chiavi uguali sono invertite. Inoltre esegue più spostamenti del necessario quando ci sono chiavi uguali.

4. Entrambi gli algoritmi sono in-place: riarrangiano gli elementi all'interno dell'array \(a\) e usano soltanto un numero costante di variabili ausiliarie (\(i\), \(j\), \(\mathit{key}\) per Insertion Sort; \(i\), \(j\), \(\mathit{minIdx}\), \(\mathit{tmp}\) per Selection Sort), indipendentemente da \(n\).

   Un metodo che non è in-place: creare un nuovo array \(b[1..n]\); per \(k \in \{1, 2, \dots, n\}\), trovare il minimo tra gli elementi di \(a\) non ancora copiati, copiarlo in \(b[k]\) e marcarlo come usato (ad esempio con un array di \(n\) flag booleani); infine restituire \(b\). Questo metodo usa memoria aggiuntiva proporzionale a \(n\) (l'array \(b\) e i flag), quindi non è in-place.

Esercizio 3.4: Algoritmi di ordinamento (E4)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [5, 2, 4, 6, 1, 3]\)

2. \(a = [8, 3, 7, 4, 9, 2]\)

3. \(a = [6, 5, 4, 3, 2, 1]\)

4. \(a = [1, 2, 3, 4, 5, 6]\)

5. \(a = [10, 5, 15, 3]\)

Domande

1. Applicare l'algoritmo InsertionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare la chiave da inserire, ogni spostamento eseguito dal ciclo interno e lo stato dell'array dopo l'inserimento.

2. Per ciascun array, contare i confronti tra chiavi \(a[j] > \mathit{key}\) e gli spostamenti eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [5, 2, 4, 6, 1, 3]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	5	2	4	6	1	3	stato iniziale
   2	1	2	5	2	4	6	1	3	\(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\)
   	0	2	5	5	4	6	1	3	\(a[1]=5>2\): sposta \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
   	\(-\)	2	2	5	4	6	1	3	\(j=0\): esci; inserisci \(a[1]\leftarrow 2\)
   3	2	4	2	5	4	6	1	3	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
   	1	4	2	5	5	6	1	3	\(a[2]=5>4\): sposta \(a[3]\leftarrow 5\); \(j\leftarrow 1\)
   	\(-\)	4	2	4	5	6	1	3	\(a[1]=2\le 4\): esci; inserisci \(a[2]\leftarrow 4\)
   4	3	6	2	4	5	6	1	3	\(\mathit{key} \leftarrow a[4]=6\); \(j \leftarrow 3\)
   	\(-\)	6	2	4	5	6	1	3	\(a[3]=5\le 6\): esci; inserisci \(a[4]\leftarrow 6\)
   5	4	1	2	4	5	6	1	3	\(\mathit{key} \leftarrow a[5]=1\); \(j \leftarrow 4\)
   	3	1	2	4	5	6	6	3	\(a[4]=6>1\): sposta \(a[5]\leftarrow 6\); \(j\leftarrow 3\)
   	2	1	2	4	5	5	6	3	\(a[3]=5>1\): sposta \(a[4]\leftarrow 5\); \(j\leftarrow 2\)
   	1	1	2	4	4	5	6	3	\(a[2]=4>1\): sposta \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
   	0	1	2	2	4	5	6	3	\(a[1]=2>1\): sposta \(a[2]\leftarrow 2\); \(j\leftarrow 0\)
   	\(-\)	1	1	2	4	5	6	3	\(j=0\): esci; inserisci \(a[1]\leftarrow 1\)
   6	5	3	1	2	4	5	6	3	\(\mathit{key} \leftarrow a[6]=3\); \(j \leftarrow 5\)
   	4	3	1	2	4	5	6	6	\(a[5]=6>3\): sposta \(a[6]\leftarrow 6\); \(j\leftarrow 4\)
   	3	3	1	2	4	5	5	6	\(a[4]=5>3\): sposta \(a[5]\leftarrow 5\); \(j\leftarrow 3\)
   	2	3	1	2	4	4	5	6	\(a[3]=4>3\): sposta \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
   	\(-\)	3	1	2	3	4	5	6	\(a[2]=2\le 3\): esci; inserisci \(a[3]\leftarrow 3\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	5	2	4	6	1	3	stato iniziale
   2	2	2	5	4	6	1	3	inserisci 2 all'inizio
   3	4	2	4	5	6	1	3	inserisci 4 tra 2 e 5
   4	6	2	4	5	6	1	3	6 già al suo posto
   5	1	1	2	4	5	6	3	inserisci 1 all'inizio
   6	3	1	2	3	4	5	6	inserisci 3 tra 2 e 4

   L'algoritmo esegue 12 confronti tra chiavi e 9 spostamenti, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

2. Array \(a = [8, 3, 7, 4, 9, 2]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	8	3	7	4	9	2	stato iniziale
   2	1	3	8	3	7	4	9	2	\(\mathit{key} \leftarrow a[2]=3\); \(j \leftarrow 1\)
   	0	3	8	8	7	4	9	2	\(a[1]=8>3\): sposta \(a[2]\leftarrow 8\); \(j\leftarrow 0\)
   	\(-\)	3	3	8	7	4	9	2	\(j=0\): esci; inserisci \(a[1]\leftarrow 3\)
   3	2	7	3	8	7	4	9	2	\(\mathit{key} \leftarrow a[3]=7\); \(j \leftarrow 2\)
   	1	7	3	8	8	4	9	2	\(a[2]=8>7\): sposta \(a[3]\leftarrow 8\); \(j\leftarrow 1\)
   	\(-\)	7	3	7	8	4	9	2	\(a[1]=3\le 7\): esci; inserisci \(a[2]\leftarrow 7\)
   4	3	4	3	7	8	4	9	2	\(\mathit{key} \leftarrow a[4]=4\); \(j \leftarrow 3\)
   	2	4	3	7	8	8	9	2	\(a[3]=8>4\): sposta \(a[4]\leftarrow 8\); \(j\leftarrow 2\)
   	1	4	3	7	7	8	9	2	\(a[2]=7>4\): sposta \(a[3]\leftarrow 7\); \(j\leftarrow 1\)
   	\(-\)	4	3	4	7	8	9	2	\(a[1]=3\le 4\): esci; inserisci \(a[2]\leftarrow 4\)
   5	4	9	3	4	7	8	9	2	\(\mathit{key} \leftarrow a[5]=9\); \(j \leftarrow 4\)
   	\(-\)	9	3	4	7	8	9	2	\(a[4]=8\le 9\): esci; inserisci \(a[5]\leftarrow 9\)
   6	5	2	3	4	7	8	9	2	\(\mathit{key} \leftarrow a[6]=2\); \(j \leftarrow 5\)
   	4	2	3	4	7	8	9	9	\(a[5]=9>2\): sposta \(a[6]\leftarrow 9\); \(j\leftarrow 4\)
   	3	2	3	4	7	8	8	9	\(a[4]=8>2\): sposta \(a[5]\leftarrow 8\); \(j\leftarrow 3\)
   	2	2	3	4	7	7	8	9	\(a[3]=7>2\): sposta \(a[4]\leftarrow 7\); \(j\leftarrow 2\)
   	1	2	3	4	4	7	8	9	\(a[2]=4>2\): sposta \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
   	0	2	3	3	4	7	8	9	\(a[1]=3>2\): sposta \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
   	\(-\)	2	2	3	4	7	8	9	\(j=0\): esci; inserisci \(a[1]\leftarrow 2\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	8	3	7	4	9	2	stato iniziale
   2	3	3	8	7	4	9	2	inserisci 3 all'inizio
   3	7	3	7	8	4	9	2	inserisci 7 tra 3 e 8
   4	4	3	4	7	8	9	2	inserisci 4 tra 3 e 7
   5	9	3	4	7	8	9	2	9 già al suo posto
   6	2	2	3	4	7	8	9	inserisci 2 all'inizio

   L'algoritmo esegue 12 confronti tra chiavi e 9 spostamenti, e l'array ordinato è

   \[ [2, 3, 4, 7, 8, 9]. \]

3. Array \(a = [6, 5, 4, 3, 2, 1]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	6	5	4	3	2	1	stato iniziale
   2	1	5	6	5	4	3	2	1	\(\mathit{key} \leftarrow a[2]=5\); \(j \leftarrow 1\)
   	0	5	6	6	4	3	2	1	\(a[1]=6>5\): sposta \(a[2]\leftarrow 6\); \(j\leftarrow 0\)
   	\(-\)	5	5	6	4	3	2	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 5\)
   3	2	4	5	6	4	3	2	1	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
   	1	4	5	6	6	3	2	1	\(a[2]=6>4\): sposta \(a[3]\leftarrow 6\); \(j\leftarrow 1\)
   	0	4	5	5	6	3	2	1	\(a[1]=5>4\): sposta \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
   	\(-\)	4	4	5	6	3	2	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 4\)
   4	3	3	4	5	6	3	2	1	\(\mathit{key} \leftarrow a[4]=3\); \(j \leftarrow 3\)
   	2	3	4	5	6	6	2	1	\(a[3]=6>3\): sposta \(a[4]\leftarrow 6\); \(j\leftarrow 2\)
   	1	3	4	5	5	6	2	1	\(a[2]=5>3\): sposta \(a[3]\leftarrow 5\); \(j\leftarrow 1\)
   	0	3	4	4	5	6	2	1	\(a[1]=4>3\): sposta \(a[2]\leftarrow 4\); \(j\leftarrow 0\)
   	\(-\)	3	3	4	5	6	2	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 3\)
   5	4	2	3	4	5	6	2	1	\(\mathit{key} \leftarrow a[5]=2\); \(j \leftarrow 4\)
   	3	2	3	4	5	6	6	1	\(a[4]=6>2\): sposta \(a[5]\leftarrow 6\); \(j\leftarrow 3\)
   	2	2	3	4	5	5	6	1	\(a[3]=5>2\): sposta \(a[4]\leftarrow 5\); \(j\leftarrow 2\)
   	1	2	3	4	4	5	6	1	\(a[2]=4>2\): sposta \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
   	0	2	3	3	4	5	6	1	\(a[1]=3>2\): sposta \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
   	\(-\)	2	2	3	4	5	6	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 2\)
   6	5	1	2	3	4	5	6	1	\(\mathit{key} \leftarrow a[6]=1\); \(j \leftarrow 5\)
   	4	1	2	3	4	5	6	6	\(a[5]=6>1\): sposta \(a[6]\leftarrow 6\); \(j\leftarrow 4\)
   	3	1	2	3	4	5	5	6	\(a[4]=5>1\): sposta \(a[5]\leftarrow 5\); \(j\leftarrow 3\)
   	2	1	2	3	4	4	5	6	\(a[3]=4>1\): sposta \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
   	1	1	2	3	3	4	5	6	\(a[2]=3>1\): sposta \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
   	0	1	2	2	3	4	5	6	\(a[1]=2>1\): sposta \(a[2]\leftarrow 2\); \(j\leftarrow 0\)
   	\(-\)	1	1	2	3	4	5	6	\(j=0\): esci; inserisci \(a[1]\leftarrow 1\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	6	5	4	3	2	1	stato iniziale
   2	5	5	6	4	3	2	1	inserisci 5 all'inizio
   3	4	4	5	6	3	2	1	inserisci 4 all'inizio
   4	3	3	4	5	6	2	1	inserisci 3 all'inizio
   5	2	2	3	4	5	6	1	inserisci 2 all'inizio
   6	1	1	2	3	4	5	6	inserisci 1 all'inizio

   L'algoritmo esegue 15 confronti tra chiavi e 15 spostamenti, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

4. Array \(a = [1, 2, 3, 4, 5, 6]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	1	2	3	4	5	6	stato iniziale
   2	1	2	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\)
   	\(-\)	2	1	2	3	4	5	6	\(a[1]=1\le 2\): esci; inserisci \(a[2]\leftarrow 2\)
   3	2	3	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[3]=3\); \(j \leftarrow 2\)
   	\(-\)	3	1	2	3	4	5	6	\(a[2]=2\le 3\): esci; inserisci \(a[3]\leftarrow 3\)
   4	3	4	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[4]=4\); \(j \leftarrow 3\)
   	\(-\)	4	1	2	3	4	5	6	\(a[3]=3\le 4\): esci; inserisci \(a[4]\leftarrow 4\)
   5	4	5	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[5]=5\); \(j \leftarrow 4\)
   	\(-\)	5	1	2	3	4	5	6	\(a[4]=4\le 5\): esci; inserisci \(a[5]\leftarrow 5\)
   6	5	6	1	2	3	4	5	6	\(\mathit{key} \leftarrow a[6]=6\); \(j \leftarrow 5\)
   	\(-\)	6	1	2	3	4	5	6	\(a[5]=5\le 6\): esci; inserisci \(a[6]\leftarrow 6\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	1	2	3	4	5	6	stato iniziale
   2	2	1	2	3	4	5	6	2 già al suo posto
   3	3	1	2	3	4	5	6	3 già al suo posto
   4	4	1	2	3	4	5	6	4 già al suo posto
   5	5	1	2	3	4	5	6	5 già al suo posto
   6	6	1	2	3	4	5	6	6 già al suo posto

   L'algoritmo esegue 5 confronti tra chiavi e 0 spostamenti, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

5. Array \(a = [10, 5, 15, 3]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	10	5	15	3	stato iniziale
   2	1	5	10	5	15	3	\(\mathit{key} \leftarrow a[2]=5\); \(j \leftarrow 1\)
   	0	5	10	10	15	3	\(a[1]=10>5\): sposta \(a[2]\leftarrow 10\); \(j\leftarrow 0\)
   	\(-\)	5	5	10	15	3	\(j=0\): esci; inserisci \(a[1]\leftarrow 5\)
   3	2	15	5	10	15	3	\(\mathit{key} \leftarrow a[3]=15\); \(j \leftarrow 2\)
   	\(-\)	15	5	10	15	3	\(a[2]=10\le 15\): esci; inserisci \(a[3]\leftarrow 15\)
   4	3	3	5	10	15	3	\(\mathit{key} \leftarrow a[4]=3\); \(j \leftarrow 3\)
   	2	3	5	10	15	15	\(a[3]=15>3\): sposta \(a[4]\leftarrow 15\); \(j\leftarrow 2\)
   	1	3	5	10	10	15	\(a[2]=10>3\): sposta \(a[3]\leftarrow 10\); \(j\leftarrow 1\)
   	0	3	5	5	10	15	\(a[1]=5>3\): sposta \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
   	\(-\)	3	3	5	10	15	\(j=0\): esci; inserisci \(a[1]\leftarrow 3\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	10	5	15	3	stato iniziale
   2	5	5	10	15	3	inserisci 5 all'inizio
   3	15	5	10	15	3	15 già al suo posto
   4	3	3	5	10	15	inserisci 3 all'inizio

   L'algoritmo esegue 5 confronti tra chiavi e 4 spostamenti, e l'array ordinato è

   \[ [3, 5, 10, 15]. \]

Esercizio 3.5: Algoritmi di ordinamento (E5)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [7, 2, 9, 4]\)

2. \(a = [15, 10, 5]\)

3. \(a = [3, 1, 4, 1, 5, 9, 2, 6]\)

4. \(a = [20, 18, 16, 14]\)

5. \(a = [11, 11, 11]\)

Domande

1. Applicare l'algoritmo InsertionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare la chiave da inserire, ogni spostamento eseguito dal ciclo interno e lo stato dell'array dopo l'inserimento.

2. Per ciascun array, contare i confronti tra chiavi \(a[j] > \mathit{key}\) e gli spostamenti eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [7, 2, 9, 4]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	7	2	9	4	stato iniziale
   2	1	2	7	2	9	4	\(\mathit{key} \leftarrow a[2]=2\); \(j \leftarrow 1\)
   	0	2	7	7	9	4	\(a[1]=7>2\): sposta \(a[2]\leftarrow 7\); \(j\leftarrow 0\)
   	\(-\)	2	2	7	9	4	\(j=0\): esci; inserisci \(a[1]\leftarrow 2\)
   3	2	9	2	7	9	4	\(\mathit{key} \leftarrow a[3]=9\); \(j \leftarrow 2\)
   	\(-\)	9	2	7	9	4	\(a[2]=7\le 9\): esci; inserisci \(a[3]\leftarrow 9\)
   4	3	4	2	7	9	4	\(\mathit{key} \leftarrow a[4]=4\); \(j \leftarrow 3\)
   	2	4	2	7	9	9	\(a[3]=9>4\): sposta \(a[4]\leftarrow 9\); \(j\leftarrow 2\)
   	1	4	2	7	7	9	\(a[2]=7>4\): sposta \(a[3]\leftarrow 7\); \(j\leftarrow 1\)
   	\(-\)	4	2	4	7	9	\(a[1]=2\le 4\): esci; inserisci \(a[2]\leftarrow 4\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	7	2	9	4	stato iniziale
   2	2	2	7	9	4	inserisci 2 all'inizio
   3	9	2	7	9	4	9 già al suo posto
   4	4	2	4	7	9	inserisci 4 tra 2 e 7

   L'algoritmo esegue 5 confronti tra chiavi e 3 spostamenti, e l'array ordinato è

   \[ [2, 4, 7, 9]. \]

2. Array \(a = [15, 10, 5]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	15	10	5	stato iniziale
   2	1	10	15	10	5	\(\mathit{key} \leftarrow a[2]=10\); \(j \leftarrow 1\)
   	0	10	15	15	5	\(a[1]=15>10\): sposta \(a[2]\leftarrow 15\); \(j\leftarrow 0\)
   	\(-\)	10	10	15	5	\(j=0\): esci; inserisci \(a[1]\leftarrow 10\)
   3	2	5	10	15	5	\(\mathit{key} \leftarrow a[3]=5\); \(j \leftarrow 2\)
   	1	5	10	15	15	\(a[2]=15>5\): sposta \(a[3]\leftarrow 15\); \(j\leftarrow 1\)
   	0	5	10	10	15	\(a[1]=10>5\): sposta \(a[2]\leftarrow 10\); \(j\leftarrow 0\)
   	\(-\)	5	5	10	15	\(j=0\): esci; inserisci \(a[1]\leftarrow 5\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	15	10	5	stato iniziale
   2	10	10	15	5	inserisci 10 all'inizio
   3	5	5	10	15	inserisci 5 all'inizio

   L'algoritmo esegue 3 confronti tra chiavi e 3 spostamenti, e l'array ordinato è

   \[ [5, 10, 15]. \]

3. Array \(a = [3, 1, 4, 1, 5, 9, 2, 6]\) (\(n=8\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Azione
   \(-\)	\(-\)	\(-\)	3	1	4	1	5	9	2	6	stato iniziale
   2	1	1	3	1	4	1	5	9	2	6	\(\mathit{key} \leftarrow a[2]=1\); \(j \leftarrow 1\)
   	0	1	3	3	4	1	5	9	2	6	\(a[1]=3>1\): sposta \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
   	\(-\)	1	1	3	4	1	5	9	2	6	\(j=0\): esci; inserisci \(a[1]\leftarrow 1\)
   3	2	4	1	3	4	1	5	9	2	6	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
   	\(-\)	4	1	3	4	1	5	9	2	6	\(a[2]=3\le 4\): esci; inserisci \(a[3]\leftarrow 4\)
   4	3	1	1	3	4	1	5	9	2	6	\(\mathit{key} \leftarrow a[4]=1\); \(j \leftarrow 3\)
   	2	1	1	3	4	4	5	9	2	6	\(a[3]=4>1\): sposta \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
   	1	1	1	3	3	4	5	9	2	6	\(a[2]=3>1\): sposta \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
   	\(-\)	1	1	1	3	4	5	9	2	6	\(a[1]=1\le 1\): esci; inserisci \(a[2]\leftarrow 1\)
   5	4	5	1	1	3	4	5	9	2	6	\(\mathit{key} \leftarrow a[5]=5\); \(j \leftarrow 4\)
   	\(-\)	5	1	1	3	4	5	9	2	6	\(a[4]=4\le 5\): esci; inserisci \(a[5]\leftarrow 5\)
   6	5	9	1	1	3	4	5	9	2	6	\(\mathit{key} \leftarrow a[6]=9\); \(j \leftarrow 5\)
   	\(-\)	9	1	1	3	4	5	9	2	6	\(a[5]=5\le 9\): esci; inserisci \(a[6]\leftarrow 9\)
   7	6	2	1	1	3	4	5	9	2	6	\(\mathit{key} \leftarrow a[7]=2\); \(j \leftarrow 6\)
   	5	2	1	1	3	4	5	9	9	6	\(a[6]=9>2\): sposta \(a[7]\leftarrow 9\); \(j\leftarrow 5\)
   	4	2	1	1	3	4	5	5	9	6	\(a[5]=5>2\): sposta \(a[6]\leftarrow 5\); \(j\leftarrow 4\)
   	3	2	1	1	3	4	4	5	9	6	\(a[4]=4>2\): sposta \(a[5]\leftarrow 4\); \(j\leftarrow 3\)
   	2	2	1	1	3	3	4	5	9	6	\(a[3]=3>2\): sposta \(a[4]\leftarrow 3\); \(j\leftarrow 2\)
   	\(-\)	2	1	1	2	3	4	5	9	6	\(a[2]=1\le 2\): esci; inserisci \(a[3]\leftarrow 2\)
   8	7	6	1	1	2	3	4	5	9	6	\(\mathit{key} \leftarrow a[8]=6\); \(j \leftarrow 7\)
   	6	6	1	1	2	3	4	5	9	9	\(a[7]=9>6\): sposta \(a[8]\leftarrow 9\); \(j\leftarrow 6\)
   	\(-\)	6	1	1	2	3	4	5	6	9	\(a[6]=5\le 6\): esci; inserisci \(a[7]\leftarrow 6\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Azione
   \(-\)	\(-\)	3	1	4	1	5	9	2	6	stato iniziale
   2	1	1	3	4	1	5	9	2	6	inserisci 1 all'inizio
   3	4	1	3	4	1	5	9	2	6	4 già al suo posto
   4	1	1	1	3	4	5	9	2	6	inserisci 1 tra 1 e 3
   5	5	1	1	3	4	5	9	2	6	5 già al suo posto
   6	9	1	1	3	4	5	9	2	6	9 già al suo posto
   7	2	1	1	2	3	4	5	9	6	inserisci 2 tra 1 e 3
   8	6	1	1	2	3	4	5	6	9	inserisci 6 tra 5 e 9

   L'algoritmo esegue 14 confronti tra chiavi e 8 spostamenti, e l'array ordinato è

   \[ [1, 1, 2, 3, 4, 5, 6, 9]. \]

4. Array \(a = [20, 18, 16, 14]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	20	18	16	14	stato iniziale
   2	1	18	20	18	16	14	\(\mathit{key} \leftarrow a[2]=18\); \(j \leftarrow 1\)
   	0	18	20	20	16	14	\(a[1]=20>18\): sposta \(a[2]\leftarrow 20\); \(j\leftarrow 0\)
   	\(-\)	18	18	20	16	14	\(j=0\): esci; inserisci \(a[1]\leftarrow 18\)
   3	2	16	18	20	16	14	\(\mathit{key} \leftarrow a[3]=16\); \(j \leftarrow 2\)
   	1	16	18	20	20	14	\(a[2]=20>16\): sposta \(a[3]\leftarrow 20\); \(j\leftarrow 1\)
   	0	16	18	18	20	14	\(a[1]=18>16\): sposta \(a[2]\leftarrow 18\); \(j\leftarrow 0\)
   	\(-\)	16	16	18	20	14	\(j=0\): esci; inserisci \(a[1]\leftarrow 16\)
   4	3	14	16	18	20	14	\(\mathit{key} \leftarrow a[4]=14\); \(j \leftarrow 3\)
   	2	14	16	18	20	20	\(a[3]=20>14\): sposta \(a[4]\leftarrow 20\); \(j\leftarrow 2\)
   	1	14	16	18	18	20	\(a[2]=18>14\): sposta \(a[3]\leftarrow 18\); \(j\leftarrow 1\)
   	0	14	16	16	18	20	\(a[1]=16>14\): sposta \(a[2]\leftarrow 16\); \(j\leftarrow 0\)
   	\(-\)	14	14	16	18	20	\(j=0\): esci; inserisci \(a[1]\leftarrow 14\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	20	18	16	14	stato iniziale
   2	18	18	20	16	14	inserisci 18 all'inizio
   3	16	16	18	20	14	inserisci 16 all'inizio
   4	14	14	16	18	20	inserisci 14 all'inizio

   L'algoritmo esegue 6 confronti tra chiavi e 6 spostamenti, e l'array ordinato è

   \[ [14, 16, 18, 20]. \]

5. Array \(a = [11, 11, 11]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	11	11	11	stato iniziale
   2	1	11	11	11	11	\(\mathit{key} \leftarrow a[2]=11\); \(j \leftarrow 1\)
   	\(-\)	11	11	11	11	\(a[1]=11\le 11\): esci; inserisci \(a[2]\leftarrow 11\)
   3	2	11	11	11	11	\(\mathit{key} \leftarrow a[3]=11\); \(j \leftarrow 2\)
   	\(-\)	11	11	11	11	\(a[2]=11\le 11\): esci; inserisci \(a[3]\leftarrow 11\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	11	11	11	stato iniziale
   2	11	11	11	11	11 già al suo posto
   3	11	11	11	11	11 già al suo posto

   L'algoritmo esegue 2 confronti tra chiavi e 0 spostamenti, e l'array ordinato è

   \[ [11, 11, 11]. \]

Esercizio 3.6: Algoritmi di ordinamento (E6)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [9, 3, 7, 2]\)

2. \(a = [12, 4, 18, 6, 10]\)

3. \(a = [5, 4, 3, 2, 1]\)

4. \(a = [100, 50, 25]\)

5. \(a = [8]\)

Domande

1. Applicare l'algoritmo InsertionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare la chiave da inserire, ogni spostamento eseguito dal ciclo interno e lo stato dell'array dopo l'inserimento.

2. Per ciascun array, contare i confronti tra chiavi \(a[j] > \mathit{key}\) e gli spostamenti eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [9, 3, 7, 2]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	9	3	7	2	stato iniziale
   2	1	3	9	3	7	2	\(\mathit{key} \leftarrow a[2]=3\); \(j \leftarrow 1\)
   	0	3	9	9	7	2	\(a[1]=9>3\): sposta \(a[2]\leftarrow 9\); \(j\leftarrow 0\)
   	\(-\)	3	3	9	7	2	\(j=0\): esci; inserisci \(a[1]\leftarrow 3\)
   3	2	7	3	9	7	2	\(\mathit{key} \leftarrow a[3]=7\); \(j \leftarrow 2\)
   	1	7	3	9	9	2	\(a[2]=9>7\): sposta \(a[3]\leftarrow 9\); \(j\leftarrow 1\)
   	\(-\)	7	3	7	9	2	\(a[1]=3\le 7\): esci; inserisci \(a[2]\leftarrow 7\)
   4	3	2	3	7	9	2	\(\mathit{key} \leftarrow a[4]=2\); \(j \leftarrow 3\)
   	2	2	3	7	9	9	\(a[3]=9>2\): sposta \(a[4]\leftarrow 9\); \(j\leftarrow 2\)
   	1	2	3	7	7	9	\(a[2]=7>2\): sposta \(a[3]\leftarrow 7\); \(j\leftarrow 1\)
   	0	2	3	3	7	9	\(a[1]=3>2\): sposta \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
   	\(-\)	2	2	3	7	9	\(j=0\): esci; inserisci \(a[1]\leftarrow 2\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	9	3	7	2	stato iniziale
   2	3	3	9	7	2	inserisci 3 all'inizio
   3	7	3	7	9	2	inserisci 7 tra 3 e 9
   4	2	2	3	7	9	inserisci 2 all'inizio

   L'algoritmo esegue 6 confronti tra chiavi e 5 spostamenti, e l'array ordinato è

   \[ [2, 3, 7, 9]. \]

2. Array \(a = [12, 4, 18, 6, 10]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	12	4	18	6	10	stato iniziale
   2	1	4	12	4	18	6	10	\(\mathit{key} \leftarrow a[2]=4\); \(j \leftarrow 1\)
   	0	4	12	12	18	6	10	\(a[1]=12>4\): sposta \(a[2]\leftarrow 12\); \(j\leftarrow 0\)
   	\(-\)	4	4	12	18	6	10	\(j=0\): esci; inserisci \(a[1]\leftarrow 4\)
   3	2	18	4	12	18	6	10	\(\mathit{key} \leftarrow a[3]=18\); \(j \leftarrow 2\)
   	\(-\)	18	4	12	18	6	10	\(a[2]=12\le 18\): esci; inserisci \(a[3]\leftarrow 18\)
   4	3	6	4	12	18	6	10	\(\mathit{key} \leftarrow a[4]=6\); \(j \leftarrow 3\)
   	2	6	4	12	18	18	10	\(a[3]=18>6\): sposta \(a[4]\leftarrow 18\); \(j\leftarrow 2\)
   	1	6	4	12	12	18	10	\(a[2]=12>6\): sposta \(a[3]\leftarrow 12\); \(j\leftarrow 1\)
   	\(-\)	6	4	6	12	18	10	\(a[1]=4\le 6\): esci; inserisci \(a[2]\leftarrow 6\)
   5	4	10	4	6	12	18	10	\(\mathit{key} \leftarrow a[5]=10\); \(j \leftarrow 4\)
   	3	10	4	6	12	18	18	\(a[4]=18>10\): sposta \(a[5]\leftarrow 18\); \(j\leftarrow 3\)
   	2	10	4	6	12	12	18	\(a[3]=12>10\): sposta \(a[4]\leftarrow 12\); \(j\leftarrow 2\)
   	\(-\)	10	4	6	10	12	18	\(a[2]=6\le 10\): esci; inserisci \(a[3]\leftarrow 10\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	12	4	18	6	10	stato iniziale
   2	4	4	12	18	6	10	inserisci 4 all'inizio
   3	18	4	12	18	6	10	18 già al suo posto
   4	6	4	6	12	18	10	inserisci 6 tra 4 e 12
   5	10	4	6	10	12	18	inserisci 10 tra 6 e 12

   L'algoritmo esegue 8 confronti tra chiavi e 5 spostamenti, e l'array ordinato è

   \[ [4, 6, 10, 12, 18]. \]

3. Array \(a = [5, 4, 3, 2, 1]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	5	4	3	2	1	stato iniziale
   2	1	4	5	4	3	2	1	\(\mathit{key} \leftarrow a[2]=4\); \(j \leftarrow 1\)
   	0	4	5	5	3	2	1	\(a[1]=5>4\): sposta \(a[2]\leftarrow 5\); \(j\leftarrow 0\)
   	\(-\)	4	4	5	3	2	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 4\)
   3	2	3	4	5	3	2	1	\(\mathit{key} \leftarrow a[3]=3\); \(j \leftarrow 2\)
   	1	3	4	5	5	2	1	\(a[2]=5>3\): sposta \(a[3]\leftarrow 5\); \(j\leftarrow 1\)
   	0	3	4	4	5	2	1	\(a[1]=4>3\): sposta \(a[2]\leftarrow 4\); \(j\leftarrow 0\)
   	\(-\)	3	3	4	5	2	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 3\)
   4	3	2	3	4	5	2	1	\(\mathit{key} \leftarrow a[4]=2\); \(j \leftarrow 3\)
   	2	2	3	4	5	5	1	\(a[3]=5>2\): sposta \(a[4]\leftarrow 5\); \(j\leftarrow 2\)
   	1	2	3	4	4	5	1	\(a[2]=4>2\): sposta \(a[3]\leftarrow 4\); \(j\leftarrow 1\)
   	0	2	3	3	4	5	1	\(a[1]=3>2\): sposta \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
   	\(-\)	2	2	3	4	5	1	\(j=0\): esci; inserisci \(a[1]\leftarrow 2\)
   5	4	1	2	3	4	5	1	\(\mathit{key} \leftarrow a[5]=1\); \(j \leftarrow 4\)
   	3	1	2	3	4	5	5	\(a[4]=5>1\): sposta \(a[5]\leftarrow 5\); \(j\leftarrow 3\)
   	2	1	2	3	4	4	5	\(a[3]=4>1\): sposta \(a[4]\leftarrow 4\); \(j\leftarrow 2\)
   	1	1	2	3	3	4	5	\(a[2]=3>1\): sposta \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
   	0	1	2	2	3	4	5	\(a[1]=2>1\): sposta \(a[2]\leftarrow 2\); \(j\leftarrow 0\)
   	\(-\)	1	1	2	3	4	5	\(j=0\): esci; inserisci \(a[1]\leftarrow 1\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	5	4	3	2	1	stato iniziale
   2	4	4	5	3	2	1	inserisci 4 all'inizio
   3	3	3	4	5	2	1	inserisci 3 all'inizio
   4	2	2	3	4	5	1	inserisci 2 all'inizio
   5	1	1	2	3	4	5	inserisci 1 all'inizio

   L'algoritmo esegue 10 confronti tra chiavi e 10 spostamenti, e l'array ordinato è

   \[ [1, 2, 3, 4, 5]. \]

4. Array \(a = [100, 50, 25]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	100	50	25	stato iniziale
   2	1	50	100	50	25	\(\mathit{key} \leftarrow a[2]=50\); \(j \leftarrow 1\)
   	0	50	100	100	25	\(a[1]=100>50\): sposta \(a[2]\leftarrow 100\); \(j\leftarrow 0\)
   	\(-\)	50	50	100	25	\(j=0\): esci; inserisci \(a[1]\leftarrow 50\)
   3	2	25	50	100	25	\(\mathit{key} \leftarrow a[3]=25\); \(j \leftarrow 2\)
   	1	25	50	100	100	\(a[2]=100>25\): sposta \(a[3]\leftarrow 100\); \(j\leftarrow 1\)
   	0	25	50	50	100	\(a[1]=50>25\): sposta \(a[2]\leftarrow 50\); \(j\leftarrow 0\)
   	\(-\)	25	25	50	100	\(j=0\): esci; inserisci \(a[1]\leftarrow 25\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	100	50	25	stato iniziale
   2	50	50	100	25	inserisci 50 all'inizio
   3	25	25	50	100	inserisci 25 all'inizio

   L'algoritmo esegue 3 confronti tra chiavi e 3 spostamenti, e l'array ordinato è

   \[ [25, 50, 100]. \]

5. Array \(a = [8]\) (\(n=1\)).

   L'array ha un solo elemento: il ciclo esterno non viene eseguito e l'array è già ordinato.

   \(a[1]\)	Azione
   8	stato iniziale: \(n=1\), il ciclo esterno non viene eseguito

   L'array ordinato è \([8]\), ottenuto senza alcun confronto tra chiavi e senza alcuno spostamento.

Esercizio 3.7: Algoritmi di ordinamento (E7)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [6, 1, 8, 2, 5]\)

2. \(a = [13, 11, 9, 7]\)

3. \(a = [2, 8, 4, 6]\)

4. \(a = [30, 20, 10]\)

5. \(a = [5, 10, 15, 20]\)

Domande

1. Applicare l'algoritmo InsertionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare la chiave da inserire, ogni spostamento eseguito dal ciclo interno e lo stato dell'array dopo l'inserimento.

2. Per ciascun array, contare i confronti tra chiavi \(a[j] > \mathit{key}\) e gli spostamenti eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [6, 1, 8, 2, 5]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	6	1	8	2	5	stato iniziale
   2	1	1	6	1	8	2	5	\(\mathit{key} \leftarrow a[2]=1\); \(j \leftarrow 1\)
   	0	1	6	6	8	2	5	\(a[1]=6>1\): sposta \(a[2]\leftarrow 6\); \(j\leftarrow 0\)
   	\(-\)	1	1	6	8	2	5	\(j=0\): esci; inserisci \(a[1]\leftarrow 1\)
   3	2	8	1	6	8	2	5	\(\mathit{key} \leftarrow a[3]=8\); \(j \leftarrow 2\)
   	\(-\)	8	1	6	8	2	5	\(a[2]=6\le 8\): esci; inserisci \(a[3]\leftarrow 8\)
   4	3	2	1	6	8	2	5	\(\mathit{key} \leftarrow a[4]=2\); \(j \leftarrow 3\)
   	2	2	1	6	8	8	5	\(a[3]=8>2\): sposta \(a[4]\leftarrow 8\); \(j\leftarrow 2\)
   	1	2	1	6	6	8	5	\(a[2]=6>2\): sposta \(a[3]\leftarrow 6\); \(j\leftarrow 1\)
   	\(-\)	2	1	2	6	8	5	\(a[1]=1\le 2\): esci; inserisci \(a[2]\leftarrow 2\)
   5	4	5	1	2	6	8	5	\(\mathit{key} \leftarrow a[5]=5\); \(j \leftarrow 4\)
   	3	5	1	2	6	8	8	\(a[4]=8>5\): sposta \(a[5]\leftarrow 8\); \(j\leftarrow 3\)
   	2	5	1	2	6	6	8	\(a[3]=6>5\): sposta \(a[4]\leftarrow 6\); \(j\leftarrow 2\)
   	\(-\)	5	1	2	5	6	8	\(a[2]=2\le 5\): esci; inserisci \(a[3]\leftarrow 5\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	6	1	8	2	5	stato iniziale
   2	1	1	6	8	2	5	inserisci 1 all'inizio
   3	8	1	6	8	2	5	8 già al suo posto
   4	2	1	2	6	8	5	inserisci 2 tra 1 e 6
   5	5	1	2	5	6	8	inserisci 5 tra 2 e 6

   L'algoritmo esegue 8 confronti tra chiavi e 5 spostamenti, e l'array ordinato è

   \[ [1, 2, 5, 6, 8]. \]

2. Array \(a = [13, 11, 9, 7]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	13	11	9	7	stato iniziale
   2	1	11	13	11	9	7	\(\mathit{key} \leftarrow a[2]=11\); \(j \leftarrow 1\)
   	0	11	13	13	9	7	\(a[1]=13>11\): sposta \(a[2]\leftarrow 13\); \(j\leftarrow 0\)
   	\(-\)	11	11	13	9	7	\(j=0\): esci; inserisci \(a[1]\leftarrow 11\)
   3	2	9	11	13	9	7	\(\mathit{key} \leftarrow a[3]=9\); \(j \leftarrow 2\)
   	1	9	11	13	13	7	\(a[2]=13>9\): sposta \(a[3]\leftarrow 13\); \(j\leftarrow 1\)
   	0	9	11	11	13	7	\(a[1]=11>9\): sposta \(a[2]\leftarrow 11\); \(j\leftarrow 0\)
   	\(-\)	9	9	11	13	7	\(j=0\): esci; inserisci \(a[1]\leftarrow 9\)
   4	3	7	9	11	13	7	\(\mathit{key} \leftarrow a[4]=7\); \(j \leftarrow 3\)
   	2	7	9	11	13	13	\(a[3]=13>7\): sposta \(a[4]\leftarrow 13\); \(j\leftarrow 2\)
   	1	7	9	11	11	13	\(a[2]=11>7\): sposta \(a[3]\leftarrow 11\); \(j\leftarrow 1\)
   	0	7	9	9	11	13	\(a[1]=9>7\): sposta \(a[2]\leftarrow 9\); \(j\leftarrow 0\)
   	\(-\)	7	7	9	11	13	\(j=0\): esci; inserisci \(a[1]\leftarrow 7\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	13	11	9	7	stato iniziale
   2	11	11	13	9	7	inserisci 11 all'inizio
   3	9	9	11	13	7	inserisci 9 all'inizio
   4	7	7	9	11	13	inserisci 7 all'inizio

   L'algoritmo esegue 6 confronti tra chiavi e 6 spostamenti, e l'array ordinato è

   \[ [7, 9, 11, 13]. \]

3. Array \(a = [2, 8, 4, 6]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	2	8	4	6	stato iniziale
   2	1	8	2	8	4	6	\(\mathit{key} \leftarrow a[2]=8\); \(j \leftarrow 1\)
   	\(-\)	8	2	8	4	6	\(a[1]=2\le 8\): esci; inserisci \(a[2]\leftarrow 8\)
   3	2	4	2	8	4	6	\(\mathit{key} \leftarrow a[3]=4\); \(j \leftarrow 2\)
   	1	4	2	8	8	6	\(a[2]=8>4\): sposta \(a[3]\leftarrow 8\); \(j\leftarrow 1\)
   	\(-\)	4	2	4	8	6	\(a[1]=2\le 4\): esci; inserisci \(a[2]\leftarrow 4\)
   4	3	6	2	4	8	6	\(\mathit{key} \leftarrow a[4]=6\); \(j \leftarrow 3\)
   	2	6	2	4	8	8	\(a[3]=8>6\): sposta \(a[4]\leftarrow 8\); \(j\leftarrow 2\)
   	\(-\)	6	2	4	6	8	\(a[2]=4\le 6\): esci; inserisci \(a[3]\leftarrow 6\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	2	8	4	6	stato iniziale
   2	8	2	8	4	6	8 già al suo posto
   3	4	2	4	8	6	inserisci 4 tra 2 e 8
   4	6	2	4	6	8	inserisci 6 tra 4 e 8

   L'algoritmo esegue 5 confronti tra chiavi e 2 spostamenti, e l'array ordinato è

   \[ [2, 4, 6, 8]. \]

4. Array \(a = [30, 20, 10]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	30	20	10	stato iniziale
   2	1	20	30	20	10	\(\mathit{key} \leftarrow a[2]=20\); \(j \leftarrow 1\)
   	0	20	30	30	10	\(a[1]=30>20\): sposta \(a[2]\leftarrow 30\); \(j\leftarrow 0\)
   	\(-\)	20	20	30	10	\(j=0\): esci; inserisci \(a[1]\leftarrow 20\)
   3	2	10	20	30	10	\(\mathit{key} \leftarrow a[3]=10\); \(j \leftarrow 2\)
   	1	10	20	30	30	\(a[2]=30>10\): sposta \(a[3]\leftarrow 30\); \(j\leftarrow 1\)
   	0	10	20	20	30	\(a[1]=20>10\): sposta \(a[2]\leftarrow 20\); \(j\leftarrow 0\)
   	\(-\)	10	10	20	30	\(j=0\): esci; inserisci \(a[1]\leftarrow 10\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	30	20	10	stato iniziale
   2	20	20	30	10	inserisci 20 all'inizio
   3	10	10	20	30	inserisci 10 all'inizio

   L'algoritmo esegue 3 confronti tra chiavi e 3 spostamenti, e l'array ordinato è

   \[ [10, 20, 30]. \]

5. Array \(a = [5, 10, 15, 20]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	5	10	15	20	stato iniziale
   2	1	10	5	10	15	20	\(\mathit{key} \leftarrow a[2]=10\); \(j \leftarrow 1\)
   	\(-\)	10	5	10	15	20	\(a[1]=5\le 10\): esci; inserisci \(a[2]\leftarrow 10\)
   3	2	15	5	10	15	20	\(\mathit{key} \leftarrow a[3]=15\); \(j \leftarrow 2\)
   	\(-\)	15	5	10	15	20	\(a[2]=10\le 15\): esci; inserisci \(a[3]\leftarrow 15\)
   4	3	20	5	10	15	20	\(\mathit{key} \leftarrow a[4]=20\); \(j \leftarrow 3\)
   	\(-\)	20	5	10	15	20	\(a[3]=15\le 20\): esci; inserisci \(a[4]\leftarrow 20\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	5	10	15	20	stato iniziale
   2	10	5	10	15	20	10 già al suo posto
   3	15	5	10	15	20	15 già al suo posto
   4	20	5	10	15	20	20 già al suo posto

   L'algoritmo esegue 3 confronti tra chiavi e 0 spostamenti, e l'array ordinato è

   \[ [5, 10, 15, 20]. \]

Esercizio 3.8: Algoritmi di ordinamento (E8)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [14, 7, 21, 3, 18]\)

2. \(a = [40, 30, 20, 10]\)

3. \(a = [3, 6, 1, 9, 2]\)

4. \(a = [25, 12, 50]\)

5. \(a = [17, 17, 17, 17]\)

Domande

1. Applicare l'algoritmo InsertionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare la chiave da inserire, ogni spostamento eseguito dal ciclo interno e lo stato dell'array dopo l'inserimento.

2. Per ciascun array, contare i confronti tra chiavi \(a[j] > \mathit{key}\) e gli spostamenti eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [14, 7, 21, 3, 18]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	14	7	21	3	18	stato iniziale
   2	1	7	14	7	21	3	18	\(\mathit{key} \leftarrow a[2]=7\); \(j \leftarrow 1\)
   	0	7	14	14	21	3	18	\(a[1]=14>7\): sposta \(a[2]\leftarrow 14\); \(j\leftarrow 0\)
   	\(-\)	7	7	14	21	3	18	\(j=0\): esci; inserisci \(a[1]\leftarrow 7\)
   3	2	21	7	14	21	3	18	\(\mathit{key} \leftarrow a[3]=21\); \(j \leftarrow 2\)
   	\(-\)	21	7	14	21	3	18	\(a[2]=14\le 21\): esci; inserisci \(a[3]\leftarrow 21\)
   4	3	3	7	14	21	3	18	\(\mathit{key} \leftarrow a[4]=3\); \(j \leftarrow 3\)
   	2	3	7	14	21	21	18	\(a[3]=21>3\): sposta \(a[4]\leftarrow 21\); \(j\leftarrow 2\)
   	1	3	7	14	14	21	18	\(a[2]=14>3\): sposta \(a[3]\leftarrow 14\); \(j\leftarrow 1\)
   	0	3	7	7	14	21	18	\(a[1]=7>3\): sposta \(a[2]\leftarrow 7\); \(j\leftarrow 0\)
   	\(-\)	3	3	7	14	21	18	\(j=0\): esci; inserisci \(a[1]\leftarrow 3\)
   5	4	18	3	7	14	21	18	\(\mathit{key} \leftarrow a[5]=18\); \(j \leftarrow 4\)
   	3	18	3	7	14	21	21	\(a[4]=21>18\): sposta \(a[5]\leftarrow 21\); \(j\leftarrow 3\)
   	\(-\)	18	3	7	14	18	21	\(a[3]=14\le 18\): esci; inserisci \(a[4]\leftarrow 18\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	14	7	21	3	18	stato iniziale
   2	7	7	14	21	3	18	inserisci 7 all'inizio
   3	21	7	14	21	3	18	21 già al suo posto
   4	3	3	7	14	21	18	inserisci 3 all'inizio
   5	18	3	7	14	18	21	inserisci 18 tra 14 e 21

   L'algoritmo esegue 7 confronti tra chiavi e 5 spostamenti, e l'array ordinato è

   \[ [3, 7, 14, 18, 21]. \]

2. Array \(a = [40, 30, 20, 10]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	40	30	20	10	stato iniziale
   2	1	30	40	30	20	10	\(\mathit{key} \leftarrow a[2]=30\); \(j \leftarrow 1\)
   	0	30	40	40	20	10	\(a[1]=40>30\): sposta \(a[2]\leftarrow 40\); \(j\leftarrow 0\)
   	\(-\)	30	30	40	20	10	\(j=0\): esci; inserisci \(a[1]\leftarrow 30\)
   3	2	20	30	40	20	10	\(\mathit{key} \leftarrow a[3]=20\); \(j \leftarrow 2\)
   	1	20	30	40	40	10	\(a[2]=40>20\): sposta \(a[3]\leftarrow 40\); \(j\leftarrow 1\)
   	0	20	30	30	40	10	\(a[1]=30>20\): sposta \(a[2]\leftarrow 30\); \(j\leftarrow 0\)
   	\(-\)	20	20	30	40	10	\(j=0\): esci; inserisci \(a[1]\leftarrow 20\)
   4	3	10	20	30	40	10	\(\mathit{key} \leftarrow a[4]=10\); \(j \leftarrow 3\)
   	2	10	20	30	40	40	\(a[3]=40>10\): sposta \(a[4]\leftarrow 40\); \(j\leftarrow 2\)
   	1	10	20	30	30	40	\(a[2]=30>10\): sposta \(a[3]\leftarrow 30\); \(j\leftarrow 1\)
   	0	10	20	20	30	40	\(a[1]=20>10\): sposta \(a[2]\leftarrow 20\); \(j\leftarrow 0\)
   	\(-\)	10	10	20	30	40	\(j=0\): esci; inserisci \(a[1]\leftarrow 10\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	40	30	20	10	stato iniziale
   2	30	30	40	20	10	inserisci 30 all'inizio
   3	20	20	30	40	10	inserisci 20 all'inizio
   4	10	10	20	30	40	inserisci 10 all'inizio

   L'algoritmo esegue 6 confronti tra chiavi e 6 spostamenti, e l'array ordinato è

   \[ [10, 20, 30, 40]. \]

3. Array \(a = [3, 6, 1, 9, 2]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	3	6	1	9	2	stato iniziale
   2	1	6	3	6	1	9	2	\(\mathit{key} \leftarrow a[2]=6\); \(j \leftarrow 1\)
   	\(-\)	6	3	6	1	9	2	\(a[1]=3\le 6\): esci; inserisci \(a[2]\leftarrow 6\)
   3	2	1	3	6	1	9	2	\(\mathit{key} \leftarrow a[3]=1\); \(j \leftarrow 2\)
   	1	1	3	6	6	9	2	\(a[2]=6>1\): sposta \(a[3]\leftarrow 6\); \(j\leftarrow 1\)
   	0	1	3	3	6	9	2	\(a[1]=3>1\): sposta \(a[2]\leftarrow 3\); \(j\leftarrow 0\)
   	\(-\)	1	1	3	6	9	2	\(j=0\): esci; inserisci \(a[1]\leftarrow 1\)
   4	3	9	1	3	6	9	2	\(\mathit{key} \leftarrow a[4]=9\); \(j \leftarrow 3\)
   	\(-\)	9	1	3	6	9	2	\(a[3]=6\le 9\): esci; inserisci \(a[4]\leftarrow 9\)
   5	4	2	1	3	6	9	2	\(\mathit{key} \leftarrow a[5]=2\); \(j \leftarrow 4\)
   	3	2	1	3	6	9	9	\(a[4]=9>2\): sposta \(a[5]\leftarrow 9\); \(j\leftarrow 3\)
   	2	2	1	3	6	6	9	\(a[3]=6>2\): sposta \(a[4]\leftarrow 6\); \(j\leftarrow 2\)
   	1	2	1	3	3	6	9	\(a[2]=3>2\): sposta \(a[3]\leftarrow 3\); \(j\leftarrow 1\)
   	\(-\)	2	1	2	3	6	9	\(a[1]=1\le 2\): esci; inserisci \(a[2]\leftarrow 2\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	3	6	1	9	2	stato iniziale
   2	6	3	6	1	9	2	6 già al suo posto
   3	1	1	3	6	9	2	inserisci 1 all'inizio
   4	9	1	3	6	9	2	9 già al suo posto
   5	2	1	2	3	6	9	inserisci 2 tra 1 e 3

   L'algoritmo esegue 8 confronti tra chiavi e 5 spostamenti, e l'array ordinato è

   \[ [1, 2, 3, 6, 9]. \]

4. Array \(a = [25, 12, 50]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	25	12	50	stato iniziale
   2	1	12	25	12	50	\(\mathit{key} \leftarrow a[2]=12\); \(j \leftarrow 1\)
   	0	12	25	25	50	\(a[1]=25>12\): sposta \(a[2]\leftarrow 25\); \(j\leftarrow 0\)
   	\(-\)	12	12	25	50	\(j=0\): esci; inserisci \(a[1]\leftarrow 12\)
   3	2	50	12	25	50	\(\mathit{key} \leftarrow a[3]=50\); \(j \leftarrow 2\)
   	\(-\)	50	12	25	50	\(a[2]=25\le 50\): esci; inserisci \(a[3]\leftarrow 50\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	25	12	50	stato iniziale
   2	12	12	25	50	inserisci 12 all'inizio
   3	50	12	25	50	50 già al suo posto

   L'algoritmo esegue 2 confronti tra chiavi e 1 spostamento, e l'array ordinato è

   \[ [12, 25, 50]. \]

5. Array \(a = [17, 17, 17, 17]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	17	17	17	17	stato iniziale
   2	1	17	17	17	17	17	\(\mathit{key} \leftarrow a[2]=17\); \(j \leftarrow 1\)
   	\(-\)	17	17	17	17	17	\(a[1]=17\le 17\): esci; inserisci \(a[2]\leftarrow 17\)
   3	2	17	17	17	17	17	\(\mathit{key} \leftarrow a[3]=17\); \(j \leftarrow 2\)
   	\(-\)	17	17	17	17	17	\(a[2]=17\le 17\): esci; inserisci \(a[3]\leftarrow 17\)
   4	3	17	17	17	17	17	\(\mathit{key} \leftarrow a[4]=17\); \(j \leftarrow 3\)
   	\(-\)	17	17	17	17	17	\(a[3]=17\le 17\): esci; inserisci \(a[4]\leftarrow 17\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{key}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	17	17	17	17	stato iniziale
   2	17	17	17	17	17	17 già al suo posto
   3	17	17	17	17	17	17 già al suo posto
   4	17	17	17	17	17	17 già al suo posto

   L'algoritmo esegue 3 confronti tra chiavi e 0 spostamenti, e l'array ordinato è

   \[ [17, 17, 17, 17]. \]

Esercizio 3.9: Algoritmi di ordinamento (E9)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [5, 2, 4, 6, 1, 3]\)

2. \(a = [8, 3, 7, 4, 9, 2]\)

3. \(a = [6, 5, 4, 3, 2, 1]\)

4. \(a = [1, 2, 3, 4, 5, 6]\)

5. \(a = [10, 5, 15, 3]\)

Domande

1. Applicare l'algoritmo ExchangeSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni confronto, dire se viene eseguito uno scambio e indicare lo stato dell'array dopo il confronto.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [5, 2, 4, 6, 1, 3]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	5	2	4	6	1	3	stato iniziale
   1	2	2	5	4	6	1	3	\(a[1]=5>a[2]=2\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	2	5	4	6	1	3	\(a[1]=2\le a[3]=4\): nessuno scambio
   	4	2	5	4	6	1	3	\(a[1]=2\le a[4]=6\): nessuno scambio
   	5	1	5	4	6	2	3	\(a[1]=2>a[5]=1\): scambia \(a[1]\leftrightarrow a[5]\)
   	6	1	5	4	6	2	3	\(a[1]=1\le a[6]=3\): nessuno scambio
   2	3	1	4	5	6	2	3	\(a[2]=5>a[3]=4\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	1	4	5	6	2	3	\(a[2]=4\le a[4]=6\): nessuno scambio
   	5	1	2	5	6	4	3	\(a[2]=4>a[5]=2\): scambia \(a[2]\leftrightarrow a[5]\)
   	6	1	2	5	6	4	3	\(a[2]=2\le a[6]=3\): nessuno scambio
   3	4	1	2	5	6	4	3	\(a[3]=5\le a[4]=6\): nessuno scambio
   	5	1	2	4	6	5	3	\(a[3]=5>a[5]=4\): scambia \(a[3]\leftrightarrow a[5]\)
   	6	1	2	3	6	5	4	\(a[3]=4>a[6]=3\): scambia \(a[3]\leftrightarrow a[6]\)
   4	5	1	2	3	5	6	4	\(a[4]=6>a[5]=5\): scambia \(a[4]\leftrightarrow a[5]\)
   	6	1	2	3	4	6	5	\(a[4]=5>a[6]=4\): scambia \(a[4]\leftrightarrow a[6]\)
   5	6	1	2	3	4	5	6	\(a[5]=6>a[6]=5\): scambia \(a[5]\leftrightarrow a[6]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	5	2	4	6	1	3	stato iniziale
   1	1	5	4	6	2	3	\(a[1]=\min(a[1..6])=1\) (2 scambi)
   2	1	2	5	6	4	3	\(a[2]=\min(a[2..6])=2\) (2 scambi)
   3	1	2	3	6	5	4	\(a[3]=\min(a[3..6])=3\) (2 scambi)
   4	1	2	3	4	6	5	\(a[4]=\min(a[4..6])=4\) (2 scambi)
   5	1	2	3	4	5	6	\(a[5]=\min(a[5..6])=5\) (1 scambio)

   L'algoritmo esegue 15 confronti tra chiavi e 9 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

2. Array \(a = [8, 3, 7, 4, 9, 2]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	8	3	7	4	9	2	stato iniziale
   1	2	3	8	7	4	9	2	\(a[1]=8>a[2]=3\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	3	8	7	4	9	2	\(a[1]=3\le a[3]=7\): nessuno scambio
   	4	3	8	7	4	9	2	\(a[1]=3\le a[4]=4\): nessuno scambio
   	5	3	8	7	4	9	2	\(a[1]=3\le a[5]=9\): nessuno scambio
   	6	2	8	7	4	9	3	\(a[1]=3>a[6]=2\): scambia \(a[1]\leftrightarrow a[6]\)
   2	3	2	7	8	4	9	3	\(a[2]=8>a[3]=7\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	2	4	8	7	9	3	\(a[2]=7>a[4]=4\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	2	4	8	7	9	3	\(a[2]=4\le a[5]=9\): nessuno scambio
   	6	2	3	8	7	9	4	\(a[2]=4>a[6]=3\): scambia \(a[2]\leftrightarrow a[6]\)
   3	4	2	3	7	8	9	4	\(a[3]=8>a[4]=7\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	2	3	7	8	9	4	\(a[3]=7\le a[5]=9\): nessuno scambio
   	6	2	3	4	8	9	7	\(a[3]=7>a[6]=4\): scambia \(a[3]\leftrightarrow a[6]\)
   4	5	2	3	4	8	9	7	\(a[4]=8\le a[5]=9\): nessuno scambio
   	6	2	3	4	7	9	8	\(a[4]=8>a[6]=7\): scambia \(a[4]\leftrightarrow a[6]\)
   5	6	2	3	4	7	8	9	\(a[5]=9>a[6]=8\): scambia \(a[5]\leftrightarrow a[6]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	8	3	7	4	9	2	stato iniziale
   1	2	8	7	4	9	3	\(a[1]=\min(a[1..6])=2\) (2 scambi)
   2	2	3	8	7	9	4	\(a[2]=\min(a[2..6])=3\) (3 scambi)
   3	2	3	4	8	9	7	\(a[3]=\min(a[3..6])=4\) (2 scambi)
   4	2	3	4	7	9	8	\(a[4]=\min(a[4..6])=7\) (1 scambio)
   5	2	3	4	7	8	9	\(a[5]=\min(a[5..6])=8\) (1 scambio)

   L'algoritmo esegue 15 confronti tra chiavi e 9 scambi, e l'array ordinato è

   \[ [2, 3, 4, 7, 8, 9]. \]

3. Array \(a = [6, 5, 4, 3, 2, 1]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	6	5	4	3	2	1	stato iniziale
   1	2	5	6	4	3	2	1	\(a[1]=6>a[2]=5\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	4	6	5	3	2	1	\(a[1]=5>a[3]=4\): scambia \(a[1]\leftrightarrow a[3]\)
   	4	3	6	5	4	2	1	\(a[1]=4>a[4]=3\): scambia \(a[1]\leftrightarrow a[4]\)
   	5	2	6	5	4	3	1	\(a[1]=3>a[5]=2\): scambia \(a[1]\leftrightarrow a[5]\)
   	6	1	6	5	4	3	2	\(a[1]=2>a[6]=1\): scambia \(a[1]\leftrightarrow a[6]\)
   2	3	1	5	6	4	3	2	\(a[2]=6>a[3]=5\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	1	4	6	5	3	2	\(a[2]=5>a[4]=4\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	1	3	6	5	4	2	\(a[2]=4>a[5]=3\): scambia \(a[2]\leftrightarrow a[5]\)
   	6	1	2	6	5	4	3	\(a[2]=3>a[6]=2\): scambia \(a[2]\leftrightarrow a[6]\)
   3	4	1	2	5	6	4	3	\(a[3]=6>a[4]=5\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	1	2	4	6	5	3	\(a[3]=5>a[5]=4\): scambia \(a[3]\leftrightarrow a[5]\)
   	6	1	2	3	6	5	4	\(a[3]=4>a[6]=3\): scambia \(a[3]\leftrightarrow a[6]\)
   4	5	1	2	3	5	6	4	\(a[4]=6>a[5]=5\): scambia \(a[4]\leftrightarrow a[5]\)
   	6	1	2	3	4	6	5	\(a[4]=5>a[6]=4\): scambia \(a[4]\leftrightarrow a[6]\)
   5	6	1	2	3	4	5	6	\(a[5]=6>a[6]=5\): scambia \(a[5]\leftrightarrow a[6]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	6	5	4	3	2	1	stato iniziale
   1	1	6	5	4	3	2	\(a[1]=\min(a[1..6])=1\) (5 scambi)
   2	1	2	6	5	4	3	\(a[2]=\min(a[2..6])=2\) (4 scambi)
   3	1	2	3	6	5	4	\(a[3]=\min(a[3..6])=3\) (3 scambi)
   4	1	2	3	4	6	5	\(a[4]=\min(a[4..6])=4\) (2 scambi)
   5	1	2	3	4	5	6	\(a[5]=\min(a[5..6])=5\) (1 scambio)

   L'algoritmo esegue 15 confronti tra chiavi e 15 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

4. Array \(a = [1, 2, 3, 4, 5, 6]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	1	2	3	4	5	6	stato iniziale
   1	2	1	2	3	4	5	6	\(a[1]=1\le a[2]=2\): nessuno scambio
   	3	1	2	3	4	5	6	\(a[1]=1\le a[3]=3\): nessuno scambio
   	4	1	2	3	4	5	6	\(a[1]=1\le a[4]=4\): nessuno scambio
   	5	1	2	3	4	5	6	\(a[1]=1\le a[5]=5\): nessuno scambio
   	6	1	2	3	4	5	6	\(a[1]=1\le a[6]=6\): nessuno scambio
   2	3	1	2	3	4	5	6	\(a[2]=2\le a[3]=3\): nessuno scambio
   	4	1	2	3	4	5	6	\(a[2]=2\le a[4]=4\): nessuno scambio
   	5	1	2	3	4	5	6	\(a[2]=2\le a[5]=5\): nessuno scambio
   	6	1	2	3	4	5	6	\(a[2]=2\le a[6]=6\): nessuno scambio
   3	4	1	2	3	4	5	6	\(a[3]=3\le a[4]=4\): nessuno scambio
   	5	1	2	3	4	5	6	\(a[3]=3\le a[5]=5\): nessuno scambio
   	6	1	2	3	4	5	6	\(a[3]=3\le a[6]=6\): nessuno scambio
   4	5	1	2	3	4	5	6	\(a[4]=4\le a[5]=5\): nessuno scambio
   	6	1	2	3	4	5	6	\(a[4]=4\le a[6]=6\): nessuno scambio
   5	6	1	2	3	4	5	6	\(a[5]=5\le a[6]=6\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	1	2	3	4	5	6	stato iniziale
   1	1	2	3	4	5	6	\(a[1]=\min(a[1..6])=1\) (0 scambi)
   2	1	2	3	4	5	6	\(a[2]=\min(a[2..6])=2\) (0 scambi)
   3	1	2	3	4	5	6	\(a[3]=\min(a[3..6])=3\) (0 scambi)
   4	1	2	3	4	5	6	\(a[4]=\min(a[4..6])=4\) (0 scambi)
   5	1	2	3	4	5	6	\(a[5]=\min(a[5..6])=5\) (0 scambi)

   L'algoritmo esegue 15 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

5. Array \(a = [10, 5, 15, 3]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	10	5	15	3	stato iniziale
   1	2	5	10	15	3	\(a[1]=10>a[2]=5\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	5	10	15	3	\(a[1]=5\le a[3]=15\): nessuno scambio
   	4	3	10	15	5	\(a[1]=5>a[4]=3\): scambia \(a[1]\leftrightarrow a[4]\)
   2	3	3	10	15	5	\(a[2]=10\le a[3]=15\): nessuno scambio
   	4	3	5	15	10	\(a[2]=10>a[4]=5\): scambia \(a[2]\leftrightarrow a[4]\)
   3	4	3	5	10	15	\(a[3]=15>a[4]=10\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	10	5	15	3	stato iniziale
   1	3	10	15	5	\(a[1]=\min(a[1..4])=3\) (2 scambi)
   2	3	5	15	10	\(a[2]=\min(a[2..4])=5\) (1 scambio)
   3	3	5	10	15	\(a[3]=\min(a[3..4])=10\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 4 scambi, e l'array ordinato è

   \[ [3, 5, 10, 15]. \]

Esercizio 3.10: Algoritmi di ordinamento (E10)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [7, 2, 9, 4]\)

2. \(a = [15, 10, 5]\)

3. \(a = [3, 1, 4, 1, 5, 9, 2, 6]\)

4. \(a = [20, 18, 16, 14]\)

5. \(a = [11, 11, 11]\)

Domande

1. Applicare l'algoritmo ExchangeSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni confronto, dire se viene eseguito uno scambio e indicare lo stato dell'array dopo il confronto.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [7, 2, 9, 4]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	7	2	9	4	stato iniziale
   1	2	2	7	9	4	\(a[1]=7>a[2]=2\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	2	7	9	4	\(a[1]=2\le a[3]=9\): nessuno scambio
   	4	2	7	9	4	\(a[1]=2\le a[4]=4\): nessuno scambio
   2	3	2	7	9	4	\(a[2]=7\le a[3]=9\): nessuno scambio
   	4	2	4	9	7	\(a[2]=7>a[4]=4\): scambia \(a[2]\leftrightarrow a[4]\)
   3	4	2	4	7	9	\(a[3]=9>a[4]=7\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	7	2	9	4	stato iniziale
   1	2	7	9	4	\(a[1]=\min(a[1..4])=2\) (1 scambio)
   2	2	4	9	7	\(a[2]=\min(a[2..4])=4\) (1 scambio)
   3	2	4	7	9	\(a[3]=\min(a[3..4])=7\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [2, 4, 7, 9]. \]

2. Array \(a = [15, 10, 5]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	15	10	5	stato iniziale
   1	2	10	15	5	\(a[1]=15>a[2]=10\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	5	15	10	\(a[1]=10>a[3]=5\): scambia \(a[1]\leftrightarrow a[3]\)
   2	3	5	10	15	\(a[2]=15>a[3]=10\): scambia \(a[2]\leftrightarrow a[3]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	15	10	5	stato iniziale
   1	5	15	10	\(a[1]=\min(a[1..3])=5\) (2 scambi)
   2	5	10	15	\(a[2]=\min(a[2..3])=10\) (1 scambio)

   L'algoritmo esegue 3 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [5, 10, 15]. \]

3. Array \(a = [3, 1, 4, 1, 5, 9, 2, 6]\) (\(n=8\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Azione
   \(-\)	\(-\)	3	1	4	1	5	9	2	6	stato iniziale
   1	2	1	3	4	1	5	9	2	6	\(a[1]=3>a[2]=1\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	1	3	4	1	5	9	2	6	\(a[1]=1\le a[3]=4\): nessuno scambio
   	4	1	3	4	1	5	9	2	6	\(a[1]=1\le a[4]=1\): nessuno scambio
   	5	1	3	4	1	5	9	2	6	\(a[1]=1\le a[5]=5\): nessuno scambio
   	6	1	3	4	1	5	9	2	6	\(a[1]=1\le a[6]=9\): nessuno scambio
   	7	1	3	4	1	5	9	2	6	\(a[1]=1\le a[7]=2\): nessuno scambio
   	8	1	3	4	1	5	9	2	6	\(a[1]=1\le a[8]=6\): nessuno scambio
   2	3	1	3	4	1	5	9	2	6	\(a[2]=3\le a[3]=4\): nessuno scambio
   	4	1	1	4	3	5	9	2	6	\(a[2]=3>a[4]=1\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	1	1	4	3	5	9	2	6	\(a[2]=1\le a[5]=5\): nessuno scambio
   	6	1	1	4	3	5	9	2	6	\(a[2]=1\le a[6]=9\): nessuno scambio
   	7	1	1	4	3	5	9	2	6	\(a[2]=1\le a[7]=2\): nessuno scambio
   	8	1	1	4	3	5	9	2	6	\(a[2]=1\le a[8]=6\): nessuno scambio
   3	4	1	1	3	4	5	9	2	6	\(a[3]=4>a[4]=3\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	1	1	3	4	5	9	2	6	\(a[3]=3\le a[5]=5\): nessuno scambio
   	6	1	1	3	4	5	9	2	6	\(a[3]=3\le a[6]=9\): nessuno scambio
   	7	1	1	2	4	5	9	3	6	\(a[3]=3>a[7]=2\): scambia \(a[3]\leftrightarrow a[7]\)
   	8	1	1	2	4	5	9	3	6	\(a[3]=2\le a[8]=6\): nessuno scambio
   4	5	1	1	2	4	5	9	3	6	\(a[4]=4\le a[5]=5\): nessuno scambio
   	6	1	1	2	4	5	9	3	6	\(a[4]=4\le a[6]=9\): nessuno scambio
   	7	1	1	2	3	5	9	4	6	\(a[4]=4>a[7]=3\): scambia \(a[4]\leftrightarrow a[7]\)
   	8	1	1	2	3	5	9	4	6	\(a[4]=3\le a[8]=6\): nessuno scambio
   5	6	1	1	2	3	5	9	4	6	\(a[5]=5\le a[6]=9\): nessuno scambio
   	7	1	1	2	3	4	9	5	6	\(a[5]=5>a[7]=4\): scambia \(a[5]\leftrightarrow a[7]\)
   	8	1	1	2	3	4	9	5	6	\(a[5]=4\le a[8]=6\): nessuno scambio
   6	7	1	1	2	3	4	5	9	6	\(a[6]=9>a[7]=5\): scambia \(a[6]\leftrightarrow a[7]\)
   	8	1	1	2	3	4	5	9	6	\(a[6]=5\le a[8]=6\): nessuno scambio
   7	8	1	1	2	3	4	5	6	9	\(a[7]=9>a[8]=6\): scambia \(a[7]\leftrightarrow a[8]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Azione
   \(-\)	3	1	4	1	5	9	2	6	stato iniziale
   1	1	3	4	1	5	9	2	6	\(a[1]=\min(a[1..8])=1\) (1 scambio)
   2	1	1	4	3	5	9	2	6	\(a[2]=\min(a[2..8])=1\) (1 scambio)
   3	1	1	2	4	5	9	3	6	\(a[3]=\min(a[3..8])=2\) (2 scambi)
   4	1	1	2	3	5	9	4	6	\(a[4]=\min(a[4..8])=3\) (1 scambio)
   5	1	1	2	3	4	9	5	6	\(a[5]=\min(a[5..8])=4\) (1 scambio)
   6	1	1	2	3	4	5	9	6	\(a[6]=\min(a[6..8])=5\) (1 scambio)
   7	1	1	2	3	4	5	6	9	\(a[7]=\min(a[7..8])=6\) (1 scambio)

   L'algoritmo esegue 28 confronti tra chiavi e 8 scambi, e l'array ordinato è

   \[ [1, 1, 2, 3, 4, 5, 6, 9]. \]

4. Array \(a = [20, 18, 16, 14]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	20	18	16	14	stato iniziale
   1	2	18	20	16	14	\(a[1]=20>a[2]=18\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	16	20	18	14	\(a[1]=18>a[3]=16\): scambia \(a[1]\leftrightarrow a[3]\)
   	4	14	20	18	16	\(a[1]=16>a[4]=14\): scambia \(a[1]\leftrightarrow a[4]\)
   2	3	14	18	20	16	\(a[2]=20>a[3]=18\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	14	16	20	18	\(a[2]=18>a[4]=16\): scambia \(a[2]\leftrightarrow a[4]\)
   3	4	14	16	18	20	\(a[3]=20>a[4]=18\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	20	18	16	14	stato iniziale
   1	14	20	18	16	\(a[1]=\min(a[1..4])=14\) (3 scambi)
   2	14	16	20	18	\(a[2]=\min(a[2..4])=16\) (2 scambi)
   3	14	16	18	20	\(a[3]=\min(a[3..4])=18\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 6 scambi, e l'array ordinato è

   \[ [14, 16, 18, 20]. \]

5. Array \(a = [11, 11, 11]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	11	11	11	stato iniziale
   1	2	11	11	11	\(a[1]=11\le a[2]=11\): nessuno scambio
   	3	11	11	11	\(a[1]=11\le a[3]=11\): nessuno scambio
   2	3	11	11	11	\(a[2]=11\le a[3]=11\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	11	11	11	stato iniziale
   1	11	11	11	\(a[1]=\min(a[1..3])=11\) (0 scambi)
   2	11	11	11	\(a[2]=\min(a[2..3])=11\) (0 scambi)

   L'algoritmo esegue 3 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [11, 11, 11]. \]

Esercizio 3.11: Algoritmi di ordinamento (E11)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [9, 3, 7, 2]\)

2. \(a = [12, 4, 18, 6, 10]\)

3. \(a = [5, 4, 3, 2, 1]\)

4. \(a = [100, 50, 25]\)

5. \(a = [8]\)

Domande

1. Applicare l'algoritmo ExchangeSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni confronto, dire se viene eseguito uno scambio e indicare lo stato dell'array dopo il confronto.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [9, 3, 7, 2]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	9	3	7	2	stato iniziale
   1	2	3	9	7	2	\(a[1]=9>a[2]=3\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	3	9	7	2	\(a[1]=3\le a[3]=7\): nessuno scambio
   	4	2	9	7	3	\(a[1]=3>a[4]=2\): scambia \(a[1]\leftrightarrow a[4]\)
   2	3	2	7	9	3	\(a[2]=9>a[3]=7\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	2	3	9	7	\(a[2]=7>a[4]=3\): scambia \(a[2]\leftrightarrow a[4]\)
   3	4	2	3	7	9	\(a[3]=9>a[4]=7\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	9	3	7	2	stato iniziale
   1	2	9	7	3	\(a[1]=\min(a[1..4])=2\) (2 scambi)
   2	2	3	9	7	\(a[2]=\min(a[2..4])=3\) (2 scambi)
   3	2	3	7	9	\(a[3]=\min(a[3..4])=7\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 5 scambi, e l'array ordinato è

   \[ [2, 3, 7, 9]. \]

2. Array \(a = [12, 4, 18, 6, 10]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	12	4	18	6	10	stato iniziale
   1	2	4	12	18	6	10	\(a[1]=12>a[2]=4\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	4	12	18	6	10	\(a[1]=4\le a[3]=18\): nessuno scambio
   	4	4	12	18	6	10	\(a[1]=4\le a[4]=6\): nessuno scambio
   	5	4	12	18	6	10	\(a[1]=4\le a[5]=10\): nessuno scambio
   2	3	4	12	18	6	10	\(a[2]=12\le a[3]=18\): nessuno scambio
   	4	4	6	18	12	10	\(a[2]=12>a[4]=6\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	4	6	18	12	10	\(a[2]=6\le a[5]=10\): nessuno scambio
   3	4	4	6	12	18	10	\(a[3]=18>a[4]=12\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	4	6	10	18	12	\(a[3]=12>a[5]=10\): scambia \(a[3]\leftrightarrow a[5]\)
   4	5	4	6	10	12	18	\(a[4]=18>a[5]=12\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	12	4	18	6	10	stato iniziale
   1	4	12	18	6	10	\(a[1]=\min(a[1..5])=4\) (1 scambio)
   2	4	6	18	12	10	\(a[2]=\min(a[2..5])=6\) (1 scambio)
   3	4	6	10	18	12	\(a[3]=\min(a[3..5])=10\) (2 scambi)
   4	4	6	10	12	18	\(a[4]=\min(a[4..5])=12\) (1 scambio)

   L'algoritmo esegue 10 confronti tra chiavi e 5 scambi, e l'array ordinato è

   \[ [4, 6, 10, 12, 18]. \]

3. Array \(a = [5, 4, 3, 2, 1]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	5	4	3	2	1	stato iniziale
   1	2	4	5	3	2	1	\(a[1]=5>a[2]=4\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	3	5	4	2	1	\(a[1]=4>a[3]=3\): scambia \(a[1]\leftrightarrow a[3]\)
   	4	2	5	4	3	1	\(a[1]=3>a[4]=2\): scambia \(a[1]\leftrightarrow a[4]\)
   	5	1	5	4	3	2	\(a[1]=2>a[5]=1\): scambia \(a[1]\leftrightarrow a[5]\)
   2	3	1	4	5	3	2	\(a[2]=5>a[3]=4\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	1	3	5	4	2	\(a[2]=4>a[4]=3\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	1	2	5	4	3	\(a[2]=3>a[5]=2\): scambia \(a[2]\leftrightarrow a[5]\)
   3	4	1	2	4	5	3	\(a[3]=5>a[4]=4\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	1	2	3	5	4	\(a[3]=4>a[5]=3\): scambia \(a[3]\leftrightarrow a[5]\)
   4	5	1	2	3	4	5	\(a[4]=5>a[5]=4\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	5	4	3	2	1	stato iniziale
   1	1	5	4	3	2	\(a[1]=\min(a[1..5])=1\) (4 scambi)
   2	1	2	5	4	3	\(a[2]=\min(a[2..5])=2\) (3 scambi)
   3	1	2	3	5	4	\(a[3]=\min(a[3..5])=3\) (2 scambi)
   4	1	2	3	4	5	\(a[4]=\min(a[4..5])=4\) (1 scambio)

   L'algoritmo esegue 10 confronti tra chiavi e 10 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5]. \]

4. Array \(a = [100, 50, 25]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	100	50	25	stato iniziale
   1	2	50	100	25	\(a[1]=100>a[2]=50\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	25	100	50	\(a[1]=50>a[3]=25\): scambia \(a[1]\leftrightarrow a[3]\)
   2	3	25	50	100	\(a[2]=100>a[3]=50\): scambia \(a[2]\leftrightarrow a[3]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	100	50	25	stato iniziale
   1	25	100	50	\(a[1]=\min(a[1..3])=25\) (2 scambi)
   2	25	50	100	\(a[2]=\min(a[2..3])=50\) (1 scambio)

   L'algoritmo esegue 3 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [25, 50, 100]. \]

5. Array \(a = [8]\) (\(n=1\)).

   L'array ha un solo elemento: il ciclo esterno non viene eseguito e l'array è già ordinato.

   \(a[1]\)	Azione
   8	stato iniziale: \(n=1\), il ciclo esterno non viene eseguito

   L'array ordinato è \([8]\), ottenuto senza alcun confronto tra chiavi e senza alcuno scambio.

Esercizio 3.12: Algoritmi di ordinamento (E12)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [6, 1, 8, 2, 5]\)

2. \(a = [13, 11, 9, 7]\)

3. \(a = [2, 8, 4, 6]\)

4. \(a = [30, 20, 10]\)

5. \(a = [5, 10, 15, 20]\)

Domande

1. Applicare l'algoritmo ExchangeSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni confronto, dire se viene eseguito uno scambio e indicare lo stato dell'array dopo il confronto.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [6, 1, 8, 2, 5]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	6	1	8	2	5	stato iniziale
   1	2	1	6	8	2	5	\(a[1]=6>a[2]=1\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	1	6	8	2	5	\(a[1]=1\le a[3]=8\): nessuno scambio
   	4	1	6	8	2	5	\(a[1]=1\le a[4]=2\): nessuno scambio
   	5	1	6	8	2	5	\(a[1]=1\le a[5]=5\): nessuno scambio
   2	3	1	6	8	2	5	\(a[2]=6\le a[3]=8\): nessuno scambio
   	4	1	2	8	6	5	\(a[2]=6>a[4]=2\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	1	2	8	6	5	\(a[2]=2\le a[5]=5\): nessuno scambio
   3	4	1	2	6	8	5	\(a[3]=8>a[4]=6\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	1	2	5	8	6	\(a[3]=6>a[5]=5\): scambia \(a[3]\leftrightarrow a[5]\)
   4	5	1	2	5	6	8	\(a[4]=8>a[5]=6\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	6	1	8	2	5	stato iniziale
   1	1	6	8	2	5	\(a[1]=\min(a[1..5])=1\) (1 scambio)
   2	1	2	8	6	5	\(a[2]=\min(a[2..5])=2\) (1 scambio)
   3	1	2	5	8	6	\(a[3]=\min(a[3..5])=5\) (2 scambi)
   4	1	2	5	6	8	\(a[4]=\min(a[4..5])=6\) (1 scambio)

   L'algoritmo esegue 10 confronti tra chiavi e 5 scambi, e l'array ordinato è

   \[ [1, 2, 5, 6, 8]. \]

2. Array \(a = [13, 11, 9, 7]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	13	11	9	7	stato iniziale
   1	2	11	13	9	7	\(a[1]=13>a[2]=11\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	9	13	11	7	\(a[1]=11>a[3]=9\): scambia \(a[1]\leftrightarrow a[3]\)
   	4	7	13	11	9	\(a[1]=9>a[4]=7\): scambia \(a[1]\leftrightarrow a[4]\)
   2	3	7	11	13	9	\(a[2]=13>a[3]=11\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	7	9	13	11	\(a[2]=11>a[4]=9\): scambia \(a[2]\leftrightarrow a[4]\)
   3	4	7	9	11	13	\(a[3]=13>a[4]=11\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	13	11	9	7	stato iniziale
   1	7	13	11	9	\(a[1]=\min(a[1..4])=7\) (3 scambi)
   2	7	9	13	11	\(a[2]=\min(a[2..4])=9\) (2 scambi)
   3	7	9	11	13	\(a[3]=\min(a[3..4])=11\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 6 scambi, e l'array ordinato è

   \[ [7, 9, 11, 13]. \]

3. Array \(a = [2, 8, 4, 6]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	2	8	4	6	stato iniziale
   1	2	2	8	4	6	\(a[1]=2\le a[2]=8\): nessuno scambio
   	3	2	8	4	6	\(a[1]=2\le a[3]=4\): nessuno scambio
   	4	2	8	4	6	\(a[1]=2\le a[4]=6\): nessuno scambio
   2	3	2	4	8	6	\(a[2]=8>a[3]=4\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	2	4	8	6	\(a[2]=4\le a[4]=6\): nessuno scambio
   3	4	2	4	6	8	\(a[3]=8>a[4]=6\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	2	8	4	6	stato iniziale
   1	2	8	4	6	\(a[1]=\min(a[1..4])=2\) (0 scambi)
   2	2	4	8	6	\(a[2]=\min(a[2..4])=4\) (1 scambio)
   3	2	4	6	8	\(a[3]=\min(a[3..4])=6\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [2, 4, 6, 8]. \]

4. Array \(a = [30, 20, 10]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	30	20	10	stato iniziale
   1	2	20	30	10	\(a[1]=30>a[2]=20\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	10	30	20	\(a[1]=20>a[3]=10\): scambia \(a[1]\leftrightarrow a[3]\)
   2	3	10	20	30	\(a[2]=30>a[3]=20\): scambia \(a[2]\leftrightarrow a[3]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	30	20	10	stato iniziale
   1	10	30	20	\(a[1]=\min(a[1..3])=10\) (2 scambi)
   2	10	20	30	\(a[2]=\min(a[2..3])=20\) (1 scambio)

   L'algoritmo esegue 3 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [10, 20, 30]. \]

5. Array \(a = [5, 10, 15, 20]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	5	10	15	20	stato iniziale
   1	2	5	10	15	20	\(a[1]=5\le a[2]=10\): nessuno scambio
   	3	5	10	15	20	\(a[1]=5\le a[3]=15\): nessuno scambio
   	4	5	10	15	20	\(a[1]=5\le a[4]=20\): nessuno scambio
   2	3	5	10	15	20	\(a[2]=10\le a[3]=15\): nessuno scambio
   	4	5	10	15	20	\(a[2]=10\le a[4]=20\): nessuno scambio
   3	4	5	10	15	20	\(a[3]=15\le a[4]=20\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	5	10	15	20	stato iniziale
   1	5	10	15	20	\(a[1]=\min(a[1..4])=5\) (0 scambi)
   2	5	10	15	20	\(a[2]=\min(a[2..4])=10\) (0 scambi)
   3	5	10	15	20	\(a[3]=\min(a[3..4])=15\) (0 scambi)

   L'algoritmo esegue 6 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [5, 10, 15, 20]. \]

Esercizio 3.13: Algoritmi di ordinamento (E13)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [14, 7, 21, 3, 18]\)

2. \(a = [40, 30, 20, 10]\)

3. \(a = [3, 6, 1, 9, 2]\)

4. \(a = [25, 12, 50]\)

5. \(a = [17, 17, 17, 17]\)

Domande

1. Applicare l'algoritmo ExchangeSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni confronto, dire se viene eseguito uno scambio e indicare lo stato dell'array dopo il confronto.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [14, 7, 21, 3, 18]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	14	7	21	3	18	stato iniziale
   1	2	7	14	21	3	18	\(a[1]=14>a[2]=7\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	7	14	21	3	18	\(a[1]=7\le a[3]=21\): nessuno scambio
   	4	3	14	21	7	18	\(a[1]=7>a[4]=3\): scambia \(a[1]\leftrightarrow a[4]\)
   	5	3	14	21	7	18	\(a[1]=3\le a[5]=18\): nessuno scambio
   2	3	3	14	21	7	18	\(a[2]=14\le a[3]=21\): nessuno scambio
   	4	3	7	21	14	18	\(a[2]=14>a[4]=7\): scambia \(a[2]\leftrightarrow a[4]\)
   	5	3	7	21	14	18	\(a[2]=7\le a[5]=18\): nessuno scambio
   3	4	3	7	14	21	18	\(a[3]=21>a[4]=14\): scambia \(a[3]\leftrightarrow a[4]\)
   	5	3	7	14	21	18	\(a[3]=14\le a[5]=18\): nessuno scambio
   4	5	3	7	14	18	21	\(a[4]=21>a[5]=18\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	14	7	21	3	18	stato iniziale
   1	3	14	21	7	18	\(a[1]=\min(a[1..5])=3\) (2 scambi)
   2	3	7	21	14	18	\(a[2]=\min(a[2..5])=7\) (1 scambio)
   3	3	7	14	21	18	\(a[3]=\min(a[3..5])=14\) (1 scambio)
   4	3	7	14	18	21	\(a[4]=\min(a[4..5])=18\) (1 scambio)

   L'algoritmo esegue 10 confronti tra chiavi e 5 scambi, e l'array ordinato è

   \[ [3, 7, 14, 18, 21]. \]

2. Array \(a = [40, 30, 20, 10]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	40	30	20	10	stato iniziale
   1	2	30	40	20	10	\(a[1]=40>a[2]=30\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	20	40	30	10	\(a[1]=30>a[3]=20\): scambia \(a[1]\leftrightarrow a[3]\)
   	4	10	40	30	20	\(a[1]=20>a[4]=10\): scambia \(a[1]\leftrightarrow a[4]\)
   2	3	10	30	40	20	\(a[2]=40>a[3]=30\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	10	20	40	30	\(a[2]=30>a[4]=20\): scambia \(a[2]\leftrightarrow a[4]\)
   3	4	10	20	30	40	\(a[3]=40>a[4]=30\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	40	30	20	10	stato iniziale
   1	10	40	30	20	\(a[1]=\min(a[1..4])=10\) (3 scambi)
   2	10	20	40	30	\(a[2]=\min(a[2..4])=20\) (2 scambi)
   3	10	20	30	40	\(a[3]=\min(a[3..4])=30\) (1 scambio)

   L'algoritmo esegue 6 confronti tra chiavi e 6 scambi, e l'array ordinato è

   \[ [10, 20, 30, 40]. \]

3. Array \(a = [3, 6, 1, 9, 2]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	3	6	1	9	2	stato iniziale
   1	2	3	6	1	9	2	\(a[1]=3\le a[2]=6\): nessuno scambio
   	3	1	6	3	9	2	\(a[1]=3>a[3]=1\): scambia \(a[1]\leftrightarrow a[3]\)
   	4	1	6	3	9	2	\(a[1]=1\le a[4]=9\): nessuno scambio
   	5	1	6	3	9	2	\(a[1]=1\le a[5]=2\): nessuno scambio
   2	3	1	3	6	9	2	\(a[2]=6>a[3]=3\): scambia \(a[2]\leftrightarrow a[3]\)
   	4	1	3	6	9	2	\(a[2]=3\le a[4]=9\): nessuno scambio
   	5	1	2	6	9	3	\(a[2]=3>a[5]=2\): scambia \(a[2]\leftrightarrow a[5]\)
   3	4	1	2	6	9	3	\(a[3]=6\le a[4]=9\): nessuno scambio
   	5	1	2	3	9	6	\(a[3]=6>a[5]=3\): scambia \(a[3]\leftrightarrow a[5]\)
   4	5	1	2	3	6	9	\(a[4]=9>a[5]=6\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	3	6	1	9	2	stato iniziale
   1	1	6	3	9	2	\(a[1]=\min(a[1..5])=1\) (1 scambio)
   2	1	2	6	9	3	\(a[2]=\min(a[2..5])=2\) (2 scambi)
   3	1	2	3	9	6	\(a[3]=\min(a[3..5])=3\) (1 scambio)
   4	1	2	3	6	9	\(a[4]=\min(a[4..5])=6\) (1 scambio)

   L'algoritmo esegue 10 confronti tra chiavi e 5 scambi, e l'array ordinato è

   \[ [1, 2, 3, 6, 9]. \]

4. Array \(a = [25, 12, 50]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	25	12	50	stato iniziale
   1	2	12	25	50	\(a[1]=25>a[2]=12\): scambia \(a[1]\leftrightarrow a[2]\)
   	3	12	25	50	\(a[1]=12\le a[3]=50\): nessuno scambio
   2	3	12	25	50	\(a[2]=25\le a[3]=50\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	25	12	50	stato iniziale
   1	12	25	50	\(a[1]=\min(a[1..3])=12\) (1 scambio)
   2	12	25	50	\(a[2]=\min(a[2..3])=25\) (0 scambi)

   L'algoritmo esegue 3 confronti tra chiavi e 1 scambio, e l'array ordinato è

   \[ [12, 25, 50]. \]

5. Array \(a = [17, 17, 17, 17]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	17	17	17	17	stato iniziale
   1	2	17	17	17	17	\(a[1]=17\le a[2]=17\): nessuno scambio
   	3	17	17	17	17	\(a[1]=17\le a[3]=17\): nessuno scambio
   	4	17	17	17	17	\(a[1]=17\le a[4]=17\): nessuno scambio
   2	3	17	17	17	17	\(a[2]=17\le a[3]=17\): nessuno scambio
   	4	17	17	17	17	\(a[2]=17\le a[4]=17\): nessuno scambio
   3	4	17	17	17	17	\(a[3]=17\le a[4]=17\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	17	17	17	17	stato iniziale
   1	17	17	17	17	\(a[1]=\min(a[1..4])=17\) (0 scambi)
   2	17	17	17	17	\(a[2]=\min(a[2..4])=17\) (0 scambi)
   3	17	17	17	17	\(a[3]=\min(a[3..4])=17\) (0 scambi)

   L'algoritmo esegue 6 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [17, 17, 17, 17]. \]

Esercizio 3.14: Algoritmi di ordinamento (E14)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [5, 2, 4, 6, 1, 3]\)

2. \(a = [8, 3, 7, 4, 9, 2]\)

3. \(a = [6, 5, 4, 3, 2, 1]\)

4. \(a = [1, 2, 3, 4, 5, 6]\)

5. \(a = [10, 5, 15, 3]\)

Domande

1. Applicare l'algoritmo SelectionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare l'indice \(\mathit{minIdx}\) del minimo trovato dal ciclo interno e dire se viene eseguito uno scambio.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [5, 2, 4, 6, 1, 3]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	5	2	4	6	1	3	stato iniziale
   1	\(-\)	1	5	2	4	6	1	3	\(\mathit{minIdx}:=1\) (\(a[1]=5\))
   	2	2	5	2	4	6	1	3	\(a[2]=2<a[1]=5\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	5	2	4	6	1	3	\(a[3]=4\ge a[2]=2\): nessun aggiornamento
   	4	2	5	2	4	6	1	3	\(a[4]=6\ge a[2]=2\): nessun aggiornamento
   	5	5	5	2	4	6	1	3	\(a[5]=1<a[2]=2\): \(\mathit{minIdx}\leftarrow 5\)
   	6	5	5	2	4	6	1	3	\(a[6]=3\ge a[5]=1\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	4	6	5	3	\(\mathit{minIdx}=5\ne 1\): scambia \(a[1]\leftrightarrow a[5]\)
   2	\(-\)	2	1	2	4	6	5	3	\(\mathit{minIdx}:=2\) (\(a[2]=2\))
   	3	2	1	2	4	6	5	3	\(a[3]=4\ge a[2]=2\): nessun aggiornamento
   	4	2	1	2	4	6	5	3	\(a[4]=6\ge a[2]=2\): nessun aggiornamento
   	5	2	1	2	4	6	5	3	\(a[5]=5\ge a[2]=2\): nessun aggiornamento
   	6	2	1	2	4	6	5	3	\(a[6]=3\ge a[2]=2\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	4	6	5	3	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	1	2	4	6	5	3	\(\mathit{minIdx}:=3\) (\(a[3]=4\))
   	4	3	1	2	4	6	5	3	\(a[4]=6\ge a[3]=4\): nessun aggiornamento
   	5	3	1	2	4	6	5	3	\(a[5]=5\ge a[3]=4\): nessun aggiornamento
   	6	6	1	2	4	6	5	3	\(a[6]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 6\)
   	\(-\)	\(-\)	1	2	3	6	5	4	\(\mathit{minIdx}=6\ne 3\): scambia \(a[3]\leftrightarrow a[6]\)
   4	\(-\)	4	1	2	3	6	5	4	\(\mathit{minIdx}:=4\) (\(a[4]=6\))
   	5	5	1	2	3	6	5	4	\(a[5]=5<a[4]=6\): \(\mathit{minIdx}\leftarrow 5\)
   	6	6	1	2	3	6	5	4	\(a[6]=4<a[5]=5\): \(\mathit{minIdx}\leftarrow 6\)
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=6\ne 4\): scambia \(a[4]\leftrightarrow a[6]\)
   5	\(-\)	5	1	2	3	4	5	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
   	6	5	1	2	3	4	5	6	\(a[6]=6\ge a[5]=5\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=5\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	5	2	4	6	1	3	stato iniziale
   1	5	1	2	4	6	5	3	scambia \(a[1]\leftrightarrow a[5]\): \(a[1]=\min(a[1..6])=1\)
   2	2	1	2	4	6	5	3	nessuno scambio: \(a[2]=\min(a[2..6])=2\)
   3	6	1	2	3	6	5	4	scambia \(a[3]\leftrightarrow a[6]\): \(a[3]=\min(a[3..6])=3\)
   4	6	1	2	3	4	5	6	scambia \(a[4]\leftrightarrow a[6]\): \(a[4]=\min(a[4..6])=4\)
   5	5	1	2	3	4	5	6	nessuno scambio: \(a[5]=\min(a[5..6])=5\)

   L'algoritmo esegue 15 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

2. Array \(a = [8, 3, 7, 4, 9, 2]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	8	3	7	4	9	2	stato iniziale
   1	\(-\)	1	8	3	7	4	9	2	\(\mathit{minIdx}:=1\) (\(a[1]=8\))
   	2	2	8	3	7	4	9	2	\(a[2]=3<a[1]=8\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	8	3	7	4	9	2	\(a[3]=7\ge a[2]=3\): nessun aggiornamento
   	4	2	8	3	7	4	9	2	\(a[4]=4\ge a[2]=3\): nessun aggiornamento
   	5	2	8	3	7	4	9	2	\(a[5]=9\ge a[2]=3\): nessun aggiornamento
   	6	6	8	3	7	4	9	2	\(a[6]=2<a[2]=3\): \(\mathit{minIdx}\leftarrow 6\)
   	\(-\)	\(-\)	2	3	7	4	9	8	\(\mathit{minIdx}=6\ne 1\): scambia \(a[1]\leftrightarrow a[6]\)
   2	\(-\)	2	2	3	7	4	9	8	\(\mathit{minIdx}:=2\) (\(a[2]=3\))
   	3	2	2	3	7	4	9	8	\(a[3]=7\ge a[2]=3\): nessun aggiornamento
   	4	2	2	3	7	4	9	8	\(a[4]=4\ge a[2]=3\): nessun aggiornamento
   	5	2	2	3	7	4	9	8	\(a[5]=9\ge a[2]=3\): nessun aggiornamento
   	6	2	2	3	7	4	9	8	\(a[6]=8\ge a[2]=3\): nessun aggiornamento
   	\(-\)	\(-\)	2	3	7	4	9	8	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	2	3	7	4	9	8	\(\mathit{minIdx}:=3\) (\(a[3]=7\))
   	4	4	2	3	7	4	9	8	\(a[4]=4<a[3]=7\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	2	3	7	4	9	8	\(a[5]=9\ge a[4]=4\): nessun aggiornamento
   	6	4	2	3	7	4	9	8	\(a[6]=8\ge a[4]=4\): nessun aggiornamento
   	\(-\)	\(-\)	2	3	4	7	9	8	\(\mathit{minIdx}=4\ne 3\): scambia \(a[3]\leftrightarrow a[4]\)
   4	\(-\)	4	2	3	4	7	9	8	\(\mathit{minIdx}:=4\) (\(a[4]=7\))
   	5	4	2	3	4	7	9	8	\(a[5]=9\ge a[4]=7\): nessun aggiornamento
   	6	4	2	3	4	7	9	8	\(a[6]=8\ge a[4]=7\): nessun aggiornamento
   	\(-\)	\(-\)	2	3	4	7	9	8	\(\mathit{minIdx}=4\): nessuno scambio
   5	\(-\)	5	2	3	4	7	9	8	\(\mathit{minIdx}:=5\) (\(a[5]=9\))
   	6	6	2	3	4	7	9	8	\(a[6]=8<a[5]=9\): \(\mathit{minIdx}\leftarrow 6\)
   	\(-\)	\(-\)	2	3	4	7	8	9	\(\mathit{minIdx}=6\ne 5\): scambia \(a[5]\leftrightarrow a[6]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	8	3	7	4	9	2	stato iniziale
   1	6	2	3	7	4	9	8	scambia \(a[1]\leftrightarrow a[6]\): \(a[1]=\min(a[1..6])=2\)
   2	2	2	3	7	4	9	8	nessuno scambio: \(a[2]=\min(a[2..6])=3\)
   3	4	2	3	4	7	9	8	scambia \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..6])=4\)
   4	4	2	3	4	7	9	8	nessuno scambio: \(a[4]=\min(a[4..6])=7\)
   5	6	2	3	4	7	8	9	scambia \(a[5]\leftrightarrow a[6]\): \(a[5]=\min(a[5..6])=8\)

   L'algoritmo esegue 15 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [2, 3, 4, 7, 8, 9]. \]

3. Array \(a = [6, 5, 4, 3, 2, 1]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	6	5	4	3	2	1	stato iniziale
   1	\(-\)	1	6	5	4	3	2	1	\(\mathit{minIdx}:=1\) (\(a[1]=6\))
   	2	2	6	5	4	3	2	1	\(a[2]=5<a[1]=6\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	6	5	4	3	2	1	\(a[3]=4<a[2]=5\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	6	5	4	3	2	1	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
   	5	5	6	5	4	3	2	1	\(a[5]=2<a[4]=3\): \(\mathit{minIdx}\leftarrow 5\)
   	6	6	6	5	4	3	2	1	\(a[6]=1<a[5]=2\): \(\mathit{minIdx}\leftarrow 6\)
   	\(-\)	\(-\)	1	5	4	3	2	6	\(\mathit{minIdx}=6\ne 1\): scambia \(a[1]\leftrightarrow a[6]\)
   2	\(-\)	2	1	5	4	3	2	6	\(\mathit{minIdx}:=2\) (\(a[2]=5\))
   	3	3	1	5	4	3	2	6	\(a[3]=4<a[2]=5\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	1	5	4	3	2	6	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
   	5	5	1	5	4	3	2	6	\(a[5]=2<a[4]=3\): \(\mathit{minIdx}\leftarrow 5\)
   	6	5	1	5	4	3	2	6	\(a[6]=6\ge a[5]=2\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	4	3	5	6	\(\mathit{minIdx}=5\ne 2\): scambia \(a[2]\leftrightarrow a[5]\)
   3	\(-\)	3	1	2	4	3	5	6	\(\mathit{minIdx}:=3\) (\(a[3]=4\))
   	4	4	1	2	4	3	5	6	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	1	2	4	3	5	6	\(a[5]=5\ge a[4]=3\): nessun aggiornamento
   	6	4	1	2	4	3	5	6	\(a[6]=6\ge a[4]=3\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=4\ne 3\): scambia \(a[3]\leftrightarrow a[4]\)
   4	\(-\)	4	1	2	3	4	5	6	\(\mathit{minIdx}:=4\) (\(a[4]=4\))
   	5	4	1	2	3	4	5	6	\(a[5]=5\ge a[4]=4\): nessun aggiornamento
   	6	4	1	2	3	4	5	6	\(a[6]=6\ge a[4]=4\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=4\): nessuno scambio
   5	\(-\)	5	1	2	3	4	5	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
   	6	5	1	2	3	4	5	6	\(a[6]=6\ge a[5]=5\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=5\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	6	5	4	3	2	1	stato iniziale
   1	6	1	5	4	3	2	6	scambia \(a[1]\leftrightarrow a[6]\): \(a[1]=\min(a[1..6])=1\)
   2	5	1	2	4	3	5	6	scambia \(a[2]\leftrightarrow a[5]\): \(a[2]=\min(a[2..6])=2\)
   3	4	1	2	3	4	5	6	scambia \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..6])=3\)
   4	4	1	2	3	4	5	6	nessuno scambio: \(a[4]=\min(a[4..6])=4\)
   5	5	1	2	3	4	5	6	nessuno scambio: \(a[5]=\min(a[5..6])=5\)

   L'algoritmo esegue 15 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

4. Array \(a = [1, 2, 3, 4, 5, 6]\) (\(n=6\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	\(-\)	1	2	3	4	5	6	stato iniziale
   1	\(-\)	1	1	2	3	4	5	6	\(\mathit{minIdx}:=1\) (\(a[1]=1\))
   	2	1	1	2	3	4	5	6	\(a[2]=2\ge a[1]=1\): nessun aggiornamento
   	3	1	1	2	3	4	5	6	\(a[3]=3\ge a[1]=1\): nessun aggiornamento
   	4	1	1	2	3	4	5	6	\(a[4]=4\ge a[1]=1\): nessun aggiornamento
   	5	1	1	2	3	4	5	6	\(a[5]=5\ge a[1]=1\): nessun aggiornamento
   	6	1	1	2	3	4	5	6	\(a[6]=6\ge a[1]=1\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=1\): nessuno scambio
   2	\(-\)	2	1	2	3	4	5	6	\(\mathit{minIdx}:=2\) (\(a[2]=2\))
   	3	2	1	2	3	4	5	6	\(a[3]=3\ge a[2]=2\): nessun aggiornamento
   	4	2	1	2	3	4	5	6	\(a[4]=4\ge a[2]=2\): nessun aggiornamento
   	5	2	1	2	3	4	5	6	\(a[5]=5\ge a[2]=2\): nessun aggiornamento
   	6	2	1	2	3	4	5	6	\(a[6]=6\ge a[2]=2\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	1	2	3	4	5	6	\(\mathit{minIdx}:=3\) (\(a[3]=3\))
   	4	3	1	2	3	4	5	6	\(a[4]=4\ge a[3]=3\): nessun aggiornamento
   	5	3	1	2	3	4	5	6	\(a[5]=5\ge a[3]=3\): nessun aggiornamento
   	6	3	1	2	3	4	5	6	\(a[6]=6\ge a[3]=3\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=3\): nessuno scambio
   4	\(-\)	4	1	2	3	4	5	6	\(\mathit{minIdx}:=4\) (\(a[4]=4\))
   	5	4	1	2	3	4	5	6	\(a[5]=5\ge a[4]=4\): nessun aggiornamento
   	6	4	1	2	3	4	5	6	\(a[6]=6\ge a[4]=4\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=4\): nessuno scambio
   5	\(-\)	5	1	2	3	4	5	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
   	6	5	1	2	3	4	5	6	\(a[6]=6\ge a[5]=5\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	6	\(\mathit{minIdx}=5\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	Azione
   \(-\)	\(-\)	1	2	3	4	5	6	stato iniziale
   1	1	1	2	3	4	5	6	nessuno scambio: \(a[1]=\min(a[1..6])=1\)
   2	2	1	2	3	4	5	6	nessuno scambio: \(a[2]=\min(a[2..6])=2\)
   3	3	1	2	3	4	5	6	nessuno scambio: \(a[3]=\min(a[3..6])=3\)
   4	4	1	2	3	4	5	6	nessuno scambio: \(a[4]=\min(a[4..6])=4\)
   5	5	1	2	3	4	5	6	nessuno scambio: \(a[5]=\min(a[5..6])=5\)

   L'algoritmo esegue 15 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5, 6]. \]

5. Array \(a = [10, 5, 15, 3]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	10	5	15	3	stato iniziale
   1	\(-\)	1	10	5	15	3	\(\mathit{minIdx}:=1\) (\(a[1]=10\))
   	2	2	10	5	15	3	\(a[2]=5<a[1]=10\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	10	5	15	3	\(a[3]=15\ge a[2]=5\): nessun aggiornamento
   	4	4	10	5	15	3	\(a[4]=3<a[2]=5\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	3	5	15	10	\(\mathit{minIdx}=4\ne 1\): scambia \(a[1]\leftrightarrow a[4]\)
   2	\(-\)	2	3	5	15	10	\(\mathit{minIdx}:=2\) (\(a[2]=5\))
   	3	2	3	5	15	10	\(a[3]=15\ge a[2]=5\): nessun aggiornamento
   	4	2	3	5	15	10	\(a[4]=10\ge a[2]=5\): nessun aggiornamento
   	\(-\)	\(-\)	3	5	15	10	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	3	5	15	10	\(\mathit{minIdx}:=3\) (\(a[3]=15\))
   	4	4	3	5	15	10	\(a[4]=10<a[3]=15\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	3	5	10	15	\(\mathit{minIdx}=4\ne 3\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	10	5	15	3	stato iniziale
   1	4	3	5	15	10	scambia \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=3\)
   2	2	3	5	15	10	nessuno scambio: \(a[2]=\min(a[2..4])=5\)
   3	4	3	5	10	15	scambia \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..4])=10\)

   L'algoritmo esegue 6 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [3, 5, 10, 15]. \]

Esercizio 3.15: Algoritmi di ordinamento (E15)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [7, 2, 9, 4]\)

2. \(a = [15, 10, 5]\)

3. \(a = [3, 1, 4, 1, 5, 9, 2, 6]\)

4. \(a = [20, 18, 16, 14]\)

5. \(a = [11, 11, 11]\)

Domande

1. Applicare l'algoritmo SelectionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare l'indice \(\mathit{minIdx}\) del minimo trovato dal ciclo interno e dire se viene eseguito uno scambio.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [7, 2, 9, 4]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	7	2	9	4	stato iniziale
   1	\(-\)	1	7	2	9	4	\(\mathit{minIdx}:=1\) (\(a[1]=7\))
   	2	2	7	2	9	4	\(a[2]=2<a[1]=7\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	7	2	9	4	\(a[3]=9\ge a[2]=2\): nessun aggiornamento
   	4	2	7	2	9	4	\(a[4]=4\ge a[2]=2\): nessun aggiornamento
   	\(-\)	\(-\)	2	7	9	4	\(\mathit{minIdx}=2\ne 1\): scambia \(a[1]\leftrightarrow a[2]\)
   2	\(-\)	2	2	7	9	4	\(\mathit{minIdx}:=2\) (\(a[2]=7\))
   	3	2	2	7	9	4	\(a[3]=9\ge a[2]=7\): nessun aggiornamento
   	4	4	2	7	9	4	\(a[4]=4<a[2]=7\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	2	4	9	7	\(\mathit{minIdx}=4\ne 2\): scambia \(a[2]\leftrightarrow a[4]\)
   3	\(-\)	3	2	4	9	7	\(\mathit{minIdx}:=3\) (\(a[3]=9\))
   	4	4	2	4	9	7	\(a[4]=7<a[3]=9\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	2	4	7	9	\(\mathit{minIdx}=4\ne 3\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	7	2	9	4	stato iniziale
   1	2	2	7	9	4	scambia \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..4])=2\)
   2	4	2	4	9	7	scambia \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..4])=4\)
   3	4	2	4	7	9	scambia \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..4])=7\)

   L'algoritmo esegue 6 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [2, 4, 7, 9]. \]

2. Array \(a = [15, 10, 5]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	15	10	5	stato iniziale
   1	\(-\)	1	15	10	5	\(\mathit{minIdx}:=1\) (\(a[1]=15\))
   	2	2	15	10	5	\(a[2]=10<a[1]=15\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	15	10	5	\(a[3]=5<a[2]=10\): \(\mathit{minIdx}\leftarrow 3\)
   	\(-\)	\(-\)	5	10	15	\(\mathit{minIdx}=3\ne 1\): scambia \(a[1]\leftrightarrow a[3]\)
   2	\(-\)	2	5	10	15	\(\mathit{minIdx}:=2\) (\(a[2]=10\))
   	3	2	5	10	15	\(a[3]=15\ge a[2]=10\): nessun aggiornamento
   	\(-\)	\(-\)	5	10	15	\(\mathit{minIdx}=2\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	15	10	5	stato iniziale
   1	3	5	10	15	scambia \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..3])=5\)
   2	2	5	10	15	nessuno scambio: \(a[2]=\min(a[2..3])=10\)

   L'algoritmo esegue 3 confronti tra chiavi e 1 scambio, e l'array ordinato è

   \[ [5, 10, 15]. \]

3. Array \(a = [3, 1, 4, 1, 5, 9, 2, 6]\) (\(n=8\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Azione
   \(-\)	\(-\)	\(-\)	3	1	4	1	5	9	2	6	stato iniziale
   1	\(-\)	1	3	1	4	1	5	9	2	6	\(\mathit{minIdx}:=1\) (\(a[1]=3\))
   	2	2	3	1	4	1	5	9	2	6	\(a[2]=1<a[1]=3\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	3	1	4	1	5	9	2	6	\(a[3]=4\ge a[2]=1\): nessun aggiornamento
   	4	2	3	1	4	1	5	9	2	6	\(a[4]=1\ge a[2]=1\): nessun aggiornamento
   	5	2	3	1	4	1	5	9	2	6	\(a[5]=5\ge a[2]=1\): nessun aggiornamento
   	6	2	3	1	4	1	5	9	2	6	\(a[6]=9\ge a[2]=1\): nessun aggiornamento
   	7	2	3	1	4	1	5	9	2	6	\(a[7]=2\ge a[2]=1\): nessun aggiornamento
   	8	2	3	1	4	1	5	9	2	6	\(a[8]=6\ge a[2]=1\): nessun aggiornamento
   	\(-\)	\(-\)	1	3	4	1	5	9	2	6	\(\mathit{minIdx}=2\ne 1\): scambia \(a[1]\leftrightarrow a[2]\)
   2	\(-\)	2	1	3	4	1	5	9	2	6	\(\mathit{minIdx}:=2\) (\(a[2]=3\))
   	3	2	1	3	4	1	5	9	2	6	\(a[3]=4\ge a[2]=3\): nessun aggiornamento
   	4	4	1	3	4	1	5	9	2	6	\(a[4]=1<a[2]=3\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	1	3	4	1	5	9	2	6	\(a[5]=5\ge a[4]=1\): nessun aggiornamento
   	6	4	1	3	4	1	5	9	2	6	\(a[6]=9\ge a[4]=1\): nessun aggiornamento
   	7	4	1	3	4	1	5	9	2	6	\(a[7]=2\ge a[4]=1\): nessun aggiornamento
   	8	4	1	3	4	1	5	9	2	6	\(a[8]=6\ge a[4]=1\): nessun aggiornamento
   	\(-\)	\(-\)	1	1	4	3	5	9	2	6	\(\mathit{minIdx}=4\ne 2\): scambia \(a[2]\leftrightarrow a[4]\)
   3	\(-\)	3	1	1	4	3	5	9	2	6	\(\mathit{minIdx}:=3\) (\(a[3]=4\))
   	4	4	1	1	4	3	5	9	2	6	\(a[4]=3<a[3]=4\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	1	1	4	3	5	9	2	6	\(a[5]=5\ge a[4]=3\): nessun aggiornamento
   	6	4	1	1	4	3	5	9	2	6	\(a[6]=9\ge a[4]=3\): nessun aggiornamento
   	7	7	1	1	4	3	5	9	2	6	\(a[7]=2<a[4]=3\): \(\mathit{minIdx}\leftarrow 7\)
   	8	7	1	1	4	3	5	9	2	6	\(a[8]=6\ge a[7]=2\): nessun aggiornamento
   	\(-\)	\(-\)	1	1	2	3	5	9	4	6	\(\mathit{minIdx}=7\ne 3\): scambia \(a[3]\leftrightarrow a[7]\)
   4	\(-\)	4	1	1	2	3	5	9	4	6	\(\mathit{minIdx}:=4\) (\(a[4]=3\))
   	5	4	1	1	2	3	5	9	4	6	\(a[5]=5\ge a[4]=3\): nessun aggiornamento
   	6	4	1	1	2	3	5	9	4	6	\(a[6]=9\ge a[4]=3\): nessun aggiornamento
   	7	4	1	1	2	3	5	9	4	6	\(a[7]=4\ge a[4]=3\): nessun aggiornamento
   	8	4	1	1	2	3	5	9	4	6	\(a[8]=6\ge a[4]=3\): nessun aggiornamento
   	\(-\)	\(-\)	1	1	2	3	5	9	4	6	\(\mathit{minIdx}=4\): nessuno scambio
   5	\(-\)	5	1	1	2	3	5	9	4	6	\(\mathit{minIdx}:=5\) (\(a[5]=5\))
   	6	5	1	1	2	3	5	9	4	6	\(a[6]=9\ge a[5]=5\): nessun aggiornamento
   	7	7	1	1	2	3	5	9	4	6	\(a[7]=4<a[5]=5\): \(\mathit{minIdx}\leftarrow 7\)
   	8	7	1	1	2	3	5	9	4	6	\(a[8]=6\ge a[7]=4\): nessun aggiornamento
   	\(-\)	\(-\)	1	1	2	3	4	9	5	6	\(\mathit{minIdx}=7\ne 5\): scambia \(a[5]\leftrightarrow a[7]\)
   6	\(-\)	6	1	1	2	3	4	9	5	6	\(\mathit{minIdx}:=6\) (\(a[6]=9\))
   	7	7	1	1	2	3	4	9	5	6	\(a[7]=5<a[6]=9\): \(\mathit{minIdx}\leftarrow 7\)
   	8	7	1	1	2	3	4	9	5	6	\(a[8]=6\ge a[7]=5\): nessun aggiornamento
   	\(-\)	\(-\)	1	1	2	3	4	5	9	6	\(\mathit{minIdx}=7\ne 6\): scambia \(a[6]\leftrightarrow a[7]\)
   7	\(-\)	7	1	1	2	3	4	5	9	6	\(\mathit{minIdx}:=7\) (\(a[7]=9\))
   	8	8	1	1	2	3	4	5	9	6	\(a[8]=6<a[7]=9\): \(\mathit{minIdx}\leftarrow 8\)
   	\(-\)	\(-\)	1	1	2	3	4	5	6	9	\(\mathit{minIdx}=8\ne 7\): scambia \(a[7]\leftrightarrow a[8]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	\(a[6]\)	\(a[7]\)	\(a[8]\)	Azione
   \(-\)	\(-\)	3	1	4	1	5	9	2	6	stato iniziale
   1	2	1	3	4	1	5	9	2	6	scambia \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..8])=1\)
   2	4	1	1	4	3	5	9	2	6	scambia \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..8])=1\)
   3	7	1	1	2	3	5	9	4	6	scambia \(a[3]\leftrightarrow a[7]\): \(a[3]=\min(a[3..8])=2\)
   4	4	1	1	2	3	5	9	4	6	nessuno scambio: \(a[4]=\min(a[4..8])=3\)
   5	7	1	1	2	3	4	9	5	6	scambia \(a[5]\leftrightarrow a[7]\): \(a[5]=\min(a[5..8])=4\)
   6	7	1	1	2	3	4	5	9	6	scambia \(a[6]\leftrightarrow a[7]\): \(a[6]=\min(a[6..8])=5\)
   7	8	1	1	2	3	4	5	6	9	scambia \(a[7]\leftrightarrow a[8]\): \(a[7]=\min(a[7..8])=6\)

   L'algoritmo esegue 28 confronti tra chiavi e 6 scambi, e l'array ordinato è

   \[ [1, 1, 2, 3, 4, 5, 6, 9]. \]

4. Array \(a = [20, 18, 16, 14]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	20	18	16	14	stato iniziale
   1	\(-\)	1	20	18	16	14	\(\mathit{minIdx}:=1\) (\(a[1]=20\))
   	2	2	20	18	16	14	\(a[2]=18<a[1]=20\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	20	18	16	14	\(a[3]=16<a[2]=18\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	20	18	16	14	\(a[4]=14<a[3]=16\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	14	18	16	20	\(\mathit{minIdx}=4\ne 1\): scambia \(a[1]\leftrightarrow a[4]\)
   2	\(-\)	2	14	18	16	20	\(\mathit{minIdx}:=2\) (\(a[2]=18\))
   	3	3	14	18	16	20	\(a[3]=16<a[2]=18\): \(\mathit{minIdx}\leftarrow 3\)
   	4	3	14	18	16	20	\(a[4]=20\ge a[3]=16\): nessun aggiornamento
   	\(-\)	\(-\)	14	16	18	20	\(\mathit{minIdx}=3\ne 2\): scambia \(a[2]\leftrightarrow a[3]\)
   3	\(-\)	3	14	16	18	20	\(\mathit{minIdx}:=3\) (\(a[3]=18\))
   	4	3	14	16	18	20	\(a[4]=20\ge a[3]=18\): nessun aggiornamento
   	\(-\)	\(-\)	14	16	18	20	\(\mathit{minIdx}=3\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	20	18	16	14	stato iniziale
   1	4	14	18	16	20	scambia \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=14\)
   2	3	14	16	18	20	scambia \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=16\)
   3	3	14	16	18	20	nessuno scambio: \(a[3]=\min(a[3..4])=18\)

   L'algoritmo esegue 6 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [14, 16, 18, 20]. \]

5. Array \(a = [11, 11, 11]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	11	11	11	stato iniziale
   1	\(-\)	1	11	11	11	\(\mathit{minIdx}:=1\) (\(a[1]=11\))
   	2	1	11	11	11	\(a[2]=11\ge a[1]=11\): nessun aggiornamento
   	3	1	11	11	11	\(a[3]=11\ge a[1]=11\): nessun aggiornamento
   	\(-\)	\(-\)	11	11	11	\(\mathit{minIdx}=1\): nessuno scambio
   2	\(-\)	2	11	11	11	\(\mathit{minIdx}:=2\) (\(a[2]=11\))
   	3	2	11	11	11	\(a[3]=11\ge a[2]=11\): nessun aggiornamento
   	\(-\)	\(-\)	11	11	11	\(\mathit{minIdx}=2\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	11	11	11	stato iniziale
   1	1	11	11	11	nessuno scambio: \(a[1]=\min(a[1..3])=11\)
   2	2	11	11	11	nessuno scambio: \(a[2]=\min(a[2..3])=11\)

   L'algoritmo esegue 3 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [11, 11, 11]. \]

Esercizio 3.16: Algoritmi di ordinamento (E16)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [9, 3, 7, 2]\)

2. \(a = [12, 4, 18, 6, 10]\)

3. \(a = [5, 4, 3, 2, 1]\)

4. \(a = [100, 50, 25]\)

5. \(a = [8]\)

Domande

1. Applicare l'algoritmo SelectionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare l'indice \(\mathit{minIdx}\) del minimo trovato dal ciclo interno e dire se viene eseguito uno scambio.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [9, 3, 7, 2]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	9	3	7	2	stato iniziale
   1	\(-\)	1	9	3	7	2	\(\mathit{minIdx}:=1\) (\(a[1]=9\))
   	2	2	9	3	7	2	\(a[2]=3<a[1]=9\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	9	3	7	2	\(a[3]=7\ge a[2]=3\): nessun aggiornamento
   	4	4	9	3	7	2	\(a[4]=2<a[2]=3\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	2	3	7	9	\(\mathit{minIdx}=4\ne 1\): scambia \(a[1]\leftrightarrow a[4]\)
   2	\(-\)	2	2	3	7	9	\(\mathit{minIdx}:=2\) (\(a[2]=3\))
   	3	2	2	3	7	9	\(a[3]=7\ge a[2]=3\): nessun aggiornamento
   	4	2	2	3	7	9	\(a[4]=9\ge a[2]=3\): nessun aggiornamento
   	\(-\)	\(-\)	2	3	7	9	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	2	3	7	9	\(\mathit{minIdx}:=3\) (\(a[3]=7\))
   	4	3	2	3	7	9	\(a[4]=9\ge a[3]=7\): nessun aggiornamento
   	\(-\)	\(-\)	2	3	7	9	\(\mathit{minIdx}=3\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	9	3	7	2	stato iniziale
   1	4	2	3	7	9	scambia \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=2\)
   2	2	2	3	7	9	nessuno scambio: \(a[2]=\min(a[2..4])=3\)
   3	3	2	3	7	9	nessuno scambio: \(a[3]=\min(a[3..4])=7\)

   L'algoritmo esegue 6 confronti tra chiavi e 1 scambio, e l'array ordinato è

   \[ [2, 3, 7, 9]. \]

2. Array \(a = [12, 4, 18, 6, 10]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	12	4	18	6	10	stato iniziale
   1	\(-\)	1	12	4	18	6	10	\(\mathit{minIdx}:=1\) (\(a[1]=12\))
   	2	2	12	4	18	6	10	\(a[2]=4<a[1]=12\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	12	4	18	6	10	\(a[3]=18\ge a[2]=4\): nessun aggiornamento
   	4	2	12	4	18	6	10	\(a[4]=6\ge a[2]=4\): nessun aggiornamento
   	5	2	12	4	18	6	10	\(a[5]=10\ge a[2]=4\): nessun aggiornamento
   	\(-\)	\(-\)	4	12	18	6	10	\(\mathit{minIdx}=2\ne 1\): scambia \(a[1]\leftrightarrow a[2]\)
   2	\(-\)	2	4	12	18	6	10	\(\mathit{minIdx}:=2\) (\(a[2]=12\))
   	3	2	4	12	18	6	10	\(a[3]=18\ge a[2]=12\): nessun aggiornamento
   	4	4	4	12	18	6	10	\(a[4]=6<a[2]=12\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	4	12	18	6	10	\(a[5]=10\ge a[4]=6\): nessun aggiornamento
   	\(-\)	\(-\)	4	6	18	12	10	\(\mathit{minIdx}=4\ne 2\): scambia \(a[2]\leftrightarrow a[4]\)
   3	\(-\)	3	4	6	18	12	10	\(\mathit{minIdx}:=3\) (\(a[3]=18\))
   	4	4	4	6	18	12	10	\(a[4]=12<a[3]=18\): \(\mathit{minIdx}\leftarrow 4\)
   	5	5	4	6	18	12	10	\(a[5]=10<a[4]=12\): \(\mathit{minIdx}\leftarrow 5\)
   	\(-\)	\(-\)	4	6	10	12	18	\(\mathit{minIdx}=5\ne 3\): scambia \(a[3]\leftrightarrow a[5]\)
   4	\(-\)	4	4	6	10	12	18	\(\mathit{minIdx}:=4\) (\(a[4]=12\))
   	5	4	4	6	10	12	18	\(a[5]=18\ge a[4]=12\): nessun aggiornamento
   	\(-\)	\(-\)	4	6	10	12	18	\(\mathit{minIdx}=4\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	12	4	18	6	10	stato iniziale
   1	2	4	12	18	6	10	scambia \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..5])=4\)
   2	4	4	6	18	12	10	scambia \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..5])=6\)
   3	5	4	6	10	12	18	scambia \(a[3]\leftrightarrow a[5]\): \(a[3]=\min(a[3..5])=10\)
   4	4	4	6	10	12	18	nessuno scambio: \(a[4]=\min(a[4..5])=12\)

   L'algoritmo esegue 10 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [4, 6, 10, 12, 18]. \]

3. Array \(a = [5, 4, 3, 2, 1]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	5	4	3	2	1	stato iniziale
   1	\(-\)	1	5	4	3	2	1	\(\mathit{minIdx}:=1\) (\(a[1]=5\))
   	2	2	5	4	3	2	1	\(a[2]=4<a[1]=5\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	5	4	3	2	1	\(a[3]=3<a[2]=4\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	5	4	3	2	1	\(a[4]=2<a[3]=3\): \(\mathit{minIdx}\leftarrow 4\)
   	5	5	5	4	3	2	1	\(a[5]=1<a[4]=2\): \(\mathit{minIdx}\leftarrow 5\)
   	\(-\)	\(-\)	1	4	3	2	5	\(\mathit{minIdx}=5\ne 1\): scambia \(a[1]\leftrightarrow a[5]\)
   2	\(-\)	2	1	4	3	2	5	\(\mathit{minIdx}:=2\) (\(a[2]=4\))
   	3	3	1	4	3	2	5	\(a[3]=3<a[2]=4\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	1	4	3	2	5	\(a[4]=2<a[3]=3\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	1	4	3	2	5	\(a[5]=5\ge a[4]=2\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	\(\mathit{minIdx}=4\ne 2\): scambia \(a[2]\leftrightarrow a[4]\)
   3	\(-\)	3	1	2	3	4	5	\(\mathit{minIdx}:=3\) (\(a[3]=3\))
   	4	3	1	2	3	4	5	\(a[4]=4\ge a[3]=3\): nessun aggiornamento
   	5	3	1	2	3	4	5	\(a[5]=5\ge a[3]=3\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	\(\mathit{minIdx}=3\): nessuno scambio
   4	\(-\)	4	1	2	3	4	5	\(\mathit{minIdx}:=4\) (\(a[4]=4\))
   	5	4	1	2	3	4	5	\(a[5]=5\ge a[4]=4\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	4	5	\(\mathit{minIdx}=4\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	5	4	3	2	1	stato iniziale
   1	5	1	4	3	2	5	scambia \(a[1]\leftrightarrow a[5]\): \(a[1]=\min(a[1..5])=1\)
   2	4	1	2	3	4	5	scambia \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..5])=2\)
   3	3	1	2	3	4	5	nessuno scambio: \(a[3]=\min(a[3..5])=3\)
   4	4	1	2	3	4	5	nessuno scambio: \(a[4]=\min(a[4..5])=4\)

   L'algoritmo esegue 10 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [1, 2, 3, 4, 5]. \]

4. Array \(a = [100, 50, 25]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	100	50	25	stato iniziale
   1	\(-\)	1	100	50	25	\(\mathit{minIdx}:=1\) (\(a[1]=100\))
   	2	2	100	50	25	\(a[2]=50<a[1]=100\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	100	50	25	\(a[3]=25<a[2]=50\): \(\mathit{minIdx}\leftarrow 3\)
   	\(-\)	\(-\)	25	50	100	\(\mathit{minIdx}=3\ne 1\): scambia \(a[1]\leftrightarrow a[3]\)
   2	\(-\)	2	25	50	100	\(\mathit{minIdx}:=2\) (\(a[2]=50\))
   	3	2	25	50	100	\(a[3]=100\ge a[2]=50\): nessun aggiornamento
   	\(-\)	\(-\)	25	50	100	\(\mathit{minIdx}=2\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	100	50	25	stato iniziale
   1	3	25	50	100	scambia \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..3])=25\)
   2	2	25	50	100	nessuno scambio: \(a[2]=\min(a[2..3])=50\)

   L'algoritmo esegue 3 confronti tra chiavi e 1 scambio, e l'array ordinato è

   \[ [25, 50, 100]. \]

5. Array \(a = [8]\) (\(n=1\)).

   L'array ha un solo elemento: il ciclo esterno non viene eseguito e l'array è già ordinato.

   \(a[1]\)	Azione
   8	stato iniziale: \(n=1\), il ciclo esterno non viene eseguito

   L'array ordinato è \([8]\), ottenuto senza alcun confronto tra chiavi e senza alcuno scambio.

Esercizio 3.17: Algoritmi di ordinamento (E17)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [6, 1, 8, 2, 5]\)

2. \(a = [13, 11, 9, 7]\)

3. \(a = [2, 8, 4, 6]\)

4. \(a = [30, 20, 10]\)

5. \(a = [5, 10, 15, 20]\)

Domande

1. Applicare l'algoritmo SelectionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare l'indice \(\mathit{minIdx}\) del minimo trovato dal ciclo interno e dire se viene eseguito uno scambio.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [6, 1, 8, 2, 5]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	6	1	8	2	5	stato iniziale
   1	\(-\)	1	6	1	8	2	5	\(\mathit{minIdx}:=1\) (\(a[1]=6\))
   	2	2	6	1	8	2	5	\(a[2]=1<a[1]=6\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	6	1	8	2	5	\(a[3]=8\ge a[2]=1\): nessun aggiornamento
   	4	2	6	1	8	2	5	\(a[4]=2\ge a[2]=1\): nessun aggiornamento
   	5	2	6	1	8	2	5	\(a[5]=5\ge a[2]=1\): nessun aggiornamento
   	\(-\)	\(-\)	1	6	8	2	5	\(\mathit{minIdx}=2\ne 1\): scambia \(a[1]\leftrightarrow a[2]\)
   2	\(-\)	2	1	6	8	2	5	\(\mathit{minIdx}:=2\) (\(a[2]=6\))
   	3	2	1	6	8	2	5	\(a[3]=8\ge a[2]=6\): nessun aggiornamento
   	4	4	1	6	8	2	5	\(a[4]=2<a[2]=6\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	1	6	8	2	5	\(a[5]=5\ge a[4]=2\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	8	6	5	\(\mathit{minIdx}=4\ne 2\): scambia \(a[2]\leftrightarrow a[4]\)
   3	\(-\)	3	1	2	8	6	5	\(\mathit{minIdx}:=3\) (\(a[3]=8\))
   	4	4	1	2	8	6	5	\(a[4]=6<a[3]=8\): \(\mathit{minIdx}\leftarrow 4\)
   	5	5	1	2	8	6	5	\(a[5]=5<a[4]=6\): \(\mathit{minIdx}\leftarrow 5\)
   	\(-\)	\(-\)	1	2	5	6	8	\(\mathit{minIdx}=5\ne 3\): scambia \(a[3]\leftrightarrow a[5]\)
   4	\(-\)	4	1	2	5	6	8	\(\mathit{minIdx}:=4\) (\(a[4]=6\))
   	5	4	1	2	5	6	8	\(a[5]=8\ge a[4]=6\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	5	6	8	\(\mathit{minIdx}=4\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	6	1	8	2	5	stato iniziale
   1	2	1	6	8	2	5	scambia \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..5])=1\)
   2	4	1	2	8	6	5	scambia \(a[2]\leftrightarrow a[4]\): \(a[2]=\min(a[2..5])=2\)
   3	5	1	2	5	6	8	scambia \(a[3]\leftrightarrow a[5]\): \(a[3]=\min(a[3..5])=5\)
   4	4	1	2	5	6	8	nessuno scambio: \(a[4]=\min(a[4..5])=6\)

   L'algoritmo esegue 10 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [1, 2, 5, 6, 8]. \]

2. Array \(a = [13, 11, 9, 7]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	13	11	9	7	stato iniziale
   1	\(-\)	1	13	11	9	7	\(\mathit{minIdx}:=1\) (\(a[1]=13\))
   	2	2	13	11	9	7	\(a[2]=11<a[1]=13\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	13	11	9	7	\(a[3]=9<a[2]=11\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	13	11	9	7	\(a[4]=7<a[3]=9\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	7	11	9	13	\(\mathit{minIdx}=4\ne 1\): scambia \(a[1]\leftrightarrow a[4]\)
   2	\(-\)	2	7	11	9	13	\(\mathit{minIdx}:=2\) (\(a[2]=11\))
   	3	3	7	11	9	13	\(a[3]=9<a[2]=11\): \(\mathit{minIdx}\leftarrow 3\)
   	4	3	7	11	9	13	\(a[4]=13\ge a[3]=9\): nessun aggiornamento
   	\(-\)	\(-\)	7	9	11	13	\(\mathit{minIdx}=3\ne 2\): scambia \(a[2]\leftrightarrow a[3]\)
   3	\(-\)	3	7	9	11	13	\(\mathit{minIdx}:=3\) (\(a[3]=11\))
   	4	3	7	9	11	13	\(a[4]=13\ge a[3]=11\): nessun aggiornamento
   	\(-\)	\(-\)	7	9	11	13	\(\mathit{minIdx}=3\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	13	11	9	7	stato iniziale
   1	4	7	11	9	13	scambia \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=7\)
   2	3	7	9	11	13	scambia \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=9\)
   3	3	7	9	11	13	nessuno scambio: \(a[3]=\min(a[3..4])=11\)

   L'algoritmo esegue 6 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [7, 9, 11, 13]. \]

3. Array \(a = [2, 8, 4, 6]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	2	8	4	6	stato iniziale
   1	\(-\)	1	2	8	4	6	\(\mathit{minIdx}:=1\) (\(a[1]=2\))
   	2	1	2	8	4	6	\(a[2]=8\ge a[1]=2\): nessun aggiornamento
   	3	1	2	8	4	6	\(a[3]=4\ge a[1]=2\): nessun aggiornamento
   	4	1	2	8	4	6	\(a[4]=6\ge a[1]=2\): nessun aggiornamento
   	\(-\)	\(-\)	2	8	4	6	\(\mathit{minIdx}=1\): nessuno scambio
   2	\(-\)	2	2	8	4	6	\(\mathit{minIdx}:=2\) (\(a[2]=8\))
   	3	3	2	8	4	6	\(a[3]=4<a[2]=8\): \(\mathit{minIdx}\leftarrow 3\)
   	4	3	2	8	4	6	\(a[4]=6\ge a[3]=4\): nessun aggiornamento
   	\(-\)	\(-\)	2	4	8	6	\(\mathit{minIdx}=3\ne 2\): scambia \(a[2]\leftrightarrow a[3]\)
   3	\(-\)	3	2	4	8	6	\(\mathit{minIdx}:=3\) (\(a[3]=8\))
   	4	4	2	4	8	6	\(a[4]=6<a[3]=8\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	2	4	6	8	\(\mathit{minIdx}=4\ne 3\): scambia \(a[3]\leftrightarrow a[4]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	2	8	4	6	stato iniziale
   1	1	2	8	4	6	nessuno scambio: \(a[1]=\min(a[1..4])=2\)
   2	3	2	4	8	6	scambia \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=4\)
   3	4	2	4	6	8	scambia \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..4])=6\)

   L'algoritmo esegue 6 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [2, 4, 6, 8]. \]

4. Array \(a = [30, 20, 10]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	30	20	10	stato iniziale
   1	\(-\)	1	30	20	10	\(\mathit{minIdx}:=1\) (\(a[1]=30\))
   	2	2	30	20	10	\(a[2]=20<a[1]=30\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	30	20	10	\(a[3]=10<a[2]=20\): \(\mathit{minIdx}\leftarrow 3\)
   	\(-\)	\(-\)	10	20	30	\(\mathit{minIdx}=3\ne 1\): scambia \(a[1]\leftrightarrow a[3]\)
   2	\(-\)	2	10	20	30	\(\mathit{minIdx}:=2\) (\(a[2]=20\))
   	3	2	10	20	30	\(a[3]=30\ge a[2]=20\): nessun aggiornamento
   	\(-\)	\(-\)	10	20	30	\(\mathit{minIdx}=2\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	30	20	10	stato iniziale
   1	3	10	20	30	scambia \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..3])=10\)
   2	2	10	20	30	nessuno scambio: \(a[2]=\min(a[2..3])=20\)

   L'algoritmo esegue 3 confronti tra chiavi e 1 scambio, e l'array ordinato è

   \[ [10, 20, 30]. \]

5. Array \(a = [5, 10, 15, 20]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	5	10	15	20	stato iniziale
   1	\(-\)	1	5	10	15	20	\(\mathit{minIdx}:=1\) (\(a[1]=5\))
   	2	1	5	10	15	20	\(a[2]=10\ge a[1]=5\): nessun aggiornamento
   	3	1	5	10	15	20	\(a[3]=15\ge a[1]=5\): nessun aggiornamento
   	4	1	5	10	15	20	\(a[4]=20\ge a[1]=5\): nessun aggiornamento
   	\(-\)	\(-\)	5	10	15	20	\(\mathit{minIdx}=1\): nessuno scambio
   2	\(-\)	2	5	10	15	20	\(\mathit{minIdx}:=2\) (\(a[2]=10\))
   	3	2	5	10	15	20	\(a[3]=15\ge a[2]=10\): nessun aggiornamento
   	4	2	5	10	15	20	\(a[4]=20\ge a[2]=10\): nessun aggiornamento
   	\(-\)	\(-\)	5	10	15	20	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	5	10	15	20	\(\mathit{minIdx}:=3\) (\(a[3]=15\))
   	4	3	5	10	15	20	\(a[4]=20\ge a[3]=15\): nessun aggiornamento
   	\(-\)	\(-\)	5	10	15	20	\(\mathit{minIdx}=3\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	5	10	15	20	stato iniziale
   1	1	5	10	15	20	nessuno scambio: \(a[1]=\min(a[1..4])=5\)
   2	2	5	10	15	20	nessuno scambio: \(a[2]=\min(a[2..4])=10\)
   3	3	5	10	15	20	nessuno scambio: \(a[3]=\min(a[3..4])=15\)

   L'algoritmo esegue 6 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [5, 10, 15, 20]. \]

Esercizio 3.18: Algoritmi di ordinamento (E18)

Consideriamo i seguenti array di numeri naturali:

1. \(a = [14, 7, 21, 3, 18]\)

2. \(a = [40, 30, 20, 10]\)

3. \(a = [3, 6, 1, 9, 2]\)

4. \(a = [25, 12, 50]\)

5. \(a = [17, 17, 17, 17]\)

Domande

1. Applicare l'algoritmo SelectionSort a ciascun array, per ordinarlo in ordine non decrescente. Mostrare l'esecuzione passo per passo: per ogni iterazione del ciclo esterno, indicare l'indice \(\mathit{minIdx}\) del minimo trovato dal ciclo interno e dire se viene eseguito uno scambio.

2. Per ciascun array, contare i confronti tra chiavi e gli scambi eseguiti dall'algoritmo.

Soluzione

Le tabelle di traccia seguono le convenzioni enunciate nell'introduzione agli esercizi di questo capitolo. Ogni punto risponde a entrambe le domande.

1. Array \(a = [14, 7, 21, 3, 18]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	14	7	21	3	18	stato iniziale
   1	\(-\)	1	14	7	21	3	18	\(\mathit{minIdx}:=1\) (\(a[1]=14\))
   	2	2	14	7	21	3	18	\(a[2]=7<a[1]=14\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	14	7	21	3	18	\(a[3]=21\ge a[2]=7\): nessun aggiornamento
   	4	4	14	7	21	3	18	\(a[4]=3<a[2]=7\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	14	7	21	3	18	\(a[5]=18\ge a[4]=3\): nessun aggiornamento
   	\(-\)	\(-\)	3	7	21	14	18	\(\mathit{minIdx}=4\ne 1\): scambia \(a[1]\leftrightarrow a[4]\)
   2	\(-\)	2	3	7	21	14	18	\(\mathit{minIdx}:=2\) (\(a[2]=7\))
   	3	2	3	7	21	14	18	\(a[3]=21\ge a[2]=7\): nessun aggiornamento
   	4	2	3	7	21	14	18	\(a[4]=14\ge a[2]=7\): nessun aggiornamento
   	5	2	3	7	21	14	18	\(a[5]=18\ge a[2]=7\): nessun aggiornamento
   	\(-\)	\(-\)	3	7	21	14	18	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	3	7	21	14	18	\(\mathit{minIdx}:=3\) (\(a[3]=21\))
   	4	4	3	7	21	14	18	\(a[4]=14<a[3]=21\): \(\mathit{minIdx}\leftarrow 4\)
   	5	4	3	7	21	14	18	\(a[5]=18\ge a[4]=14\): nessun aggiornamento
   	\(-\)	\(-\)	3	7	14	21	18	\(\mathit{minIdx}=4\ne 3\): scambia \(a[3]\leftrightarrow a[4]\)
   4	\(-\)	4	3	7	14	21	18	\(\mathit{minIdx}:=4\) (\(a[4]=21\))
   	5	5	3	7	14	21	18	\(a[5]=18<a[4]=21\): \(\mathit{minIdx}\leftarrow 5\)
   	\(-\)	\(-\)	3	7	14	18	21	\(\mathit{minIdx}=5\ne 4\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	14	7	21	3	18	stato iniziale
   1	4	3	7	21	14	18	scambia \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..5])=3\)
   2	2	3	7	21	14	18	nessuno scambio: \(a[2]=\min(a[2..5])=7\)
   3	4	3	7	14	21	18	scambia \(a[3]\leftrightarrow a[4]\): \(a[3]=\min(a[3..5])=14\)
   4	5	3	7	14	18	21	scambia \(a[4]\leftrightarrow a[5]\): \(a[4]=\min(a[4..5])=18\)

   L'algoritmo esegue 10 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [3, 7, 14, 18, 21]. \]

2. Array \(a = [40, 30, 20, 10]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	40	30	20	10	stato iniziale
   1	\(-\)	1	40	30	20	10	\(\mathit{minIdx}:=1\) (\(a[1]=40\))
   	2	2	40	30	20	10	\(a[2]=30<a[1]=40\): \(\mathit{minIdx}\leftarrow 2\)
   	3	3	40	30	20	10	\(a[3]=20<a[2]=30\): \(\mathit{minIdx}\leftarrow 3\)
   	4	4	40	30	20	10	\(a[4]=10<a[3]=20\): \(\mathit{minIdx}\leftarrow 4\)
   	\(-\)	\(-\)	10	30	20	40	\(\mathit{minIdx}=4\ne 1\): scambia \(a[1]\leftrightarrow a[4]\)
   2	\(-\)	2	10	30	20	40	\(\mathit{minIdx}:=2\) (\(a[2]=30\))
   	3	3	10	30	20	40	\(a[3]=20<a[2]=30\): \(\mathit{minIdx}\leftarrow 3\)
   	4	3	10	30	20	40	\(a[4]=40\ge a[3]=20\): nessun aggiornamento
   	\(-\)	\(-\)	10	20	30	40	\(\mathit{minIdx}=3\ne 2\): scambia \(a[2]\leftrightarrow a[3]\)
   3	\(-\)	3	10	20	30	40	\(\mathit{minIdx}:=3\) (\(a[3]=30\))
   	4	3	10	20	30	40	\(a[4]=40\ge a[3]=30\): nessun aggiornamento
   	\(-\)	\(-\)	10	20	30	40	\(\mathit{minIdx}=3\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	40	30	20	10	stato iniziale
   1	4	10	30	20	40	scambia \(a[1]\leftrightarrow a[4]\): \(a[1]=\min(a[1..4])=10\)
   2	3	10	20	30	40	scambia \(a[2]\leftrightarrow a[3]\): \(a[2]=\min(a[2..4])=20\)
   3	3	10	20	30	40	nessuno scambio: \(a[3]=\min(a[3..4])=30\)

   L'algoritmo esegue 6 confronti tra chiavi e 2 scambi, e l'array ordinato è

   \[ [10, 20, 30, 40]. \]

3. Array \(a = [3, 6, 1, 9, 2]\) (\(n=5\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	\(-\)	3	6	1	9	2	stato iniziale
   1	\(-\)	1	3	6	1	9	2	\(\mathit{minIdx}:=1\) (\(a[1]=3\))
   	2	1	3	6	1	9	2	\(a[2]=6\ge a[1]=3\): nessun aggiornamento
   	3	3	3	6	1	9	2	\(a[3]=1<a[1]=3\): \(\mathit{minIdx}\leftarrow 3\)
   	4	3	3	6	1	9	2	\(a[4]=9\ge a[3]=1\): nessun aggiornamento
   	5	3	3	6	1	9	2	\(a[5]=2\ge a[3]=1\): nessun aggiornamento
   	\(-\)	\(-\)	1	6	3	9	2	\(\mathit{minIdx}=3\ne 1\): scambia \(a[1]\leftrightarrow a[3]\)
   2	\(-\)	2	1	6	3	9	2	\(\mathit{minIdx}:=2\) (\(a[2]=6\))
   	3	3	1	6	3	9	2	\(a[3]=3<a[2]=6\): \(\mathit{minIdx}\leftarrow 3\)
   	4	3	1	6	3	9	2	\(a[4]=9\ge a[3]=3\): nessun aggiornamento
   	5	5	1	6	3	9	2	\(a[5]=2<a[3]=3\): \(\mathit{minIdx}\leftarrow 5\)
   	\(-\)	\(-\)	1	2	3	9	6	\(\mathit{minIdx}=5\ne 2\): scambia \(a[2]\leftrightarrow a[5]\)
   3	\(-\)	3	1	2	3	9	6	\(\mathit{minIdx}:=3\) (\(a[3]=3\))
   	4	3	1	2	3	9	6	\(a[4]=9\ge a[3]=3\): nessun aggiornamento
   	5	3	1	2	3	9	6	\(a[5]=6\ge a[3]=3\): nessun aggiornamento
   	\(-\)	\(-\)	1	2	3	9	6	\(\mathit{minIdx}=3\): nessuno scambio
   4	\(-\)	4	1	2	3	9	6	\(\mathit{minIdx}:=4\) (\(a[4]=9\))
   	5	5	1	2	3	9	6	\(a[5]=6<a[4]=9\): \(\mathit{minIdx}\leftarrow 5\)
   	\(-\)	\(-\)	1	2	3	6	9	\(\mathit{minIdx}=5\ne 4\): scambia \(a[4]\leftrightarrow a[5]\)

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	\(a[5]\)	Azione
   \(-\)	\(-\)	3	6	1	9	2	stato iniziale
   1	3	1	6	3	9	2	scambia \(a[1]\leftrightarrow a[3]\): \(a[1]=\min(a[1..5])=1\)
   2	5	1	2	3	9	6	scambia \(a[2]\leftrightarrow a[5]\): \(a[2]=\min(a[2..5])=2\)
   3	3	1	2	3	9	6	nessuno scambio: \(a[3]=\min(a[3..5])=3\)
   4	5	1	2	3	6	9	scambia \(a[4]\leftrightarrow a[5]\): \(a[4]=\min(a[4..5])=6\)

   L'algoritmo esegue 10 confronti tra chiavi e 3 scambi, e l'array ordinato è

   \[ [1, 2, 3, 6, 9]. \]

4. Array \(a = [25, 12, 50]\) (\(n=3\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	\(-\)	25	12	50	stato iniziale
   1	\(-\)	1	25	12	50	\(\mathit{minIdx}:=1\) (\(a[1]=25\))
   	2	2	25	12	50	\(a[2]=12<a[1]=25\): \(\mathit{minIdx}\leftarrow 2\)
   	3	2	25	12	50	\(a[3]=50\ge a[2]=12\): nessun aggiornamento
   	\(-\)	\(-\)	12	25	50	\(\mathit{minIdx}=2\ne 1\): scambia \(a[1]\leftrightarrow a[2]\)
   2	\(-\)	2	12	25	50	\(\mathit{minIdx}:=2\) (\(a[2]=25\))
   	3	2	12	25	50	\(a[3]=50\ge a[2]=25\): nessun aggiornamento
   	\(-\)	\(-\)	12	25	50	\(\mathit{minIdx}=2\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	Azione
   \(-\)	\(-\)	25	12	50	stato iniziale
   1	2	12	25	50	scambia \(a[1]\leftrightarrow a[2]\): \(a[1]=\min(a[1..3])=12\)
   2	2	12	25	50	nessuno scambio: \(a[2]=\min(a[2..3])=25\)

   L'algoritmo esegue 3 confronti tra chiavi e 1 scambio, e l'array ordinato è

   \[ [12, 25, 50]. \]

5. Array \(a = [17, 17, 17, 17]\) (\(n=4\)).

   Traccia dettagliata:

   \(i\)	\(j\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	\(-\)	17	17	17	17	stato iniziale
   1	\(-\)	1	17	17	17	17	\(\mathit{minIdx}:=1\) (\(a[1]=17\))
   	2	1	17	17	17	17	\(a[2]=17\ge a[1]=17\): nessun aggiornamento
   	3	1	17	17	17	17	\(a[3]=17\ge a[1]=17\): nessun aggiornamento
   	4	1	17	17	17	17	\(a[4]=17\ge a[1]=17\): nessun aggiornamento
   	\(-\)	\(-\)	17	17	17	17	\(\mathit{minIdx}=1\): nessuno scambio
   2	\(-\)	2	17	17	17	17	\(\mathit{minIdx}:=2\) (\(a[2]=17\))
   	3	2	17	17	17	17	\(a[3]=17\ge a[2]=17\): nessun aggiornamento
   	4	2	17	17	17	17	\(a[4]=17\ge a[2]=17\): nessun aggiornamento
   	\(-\)	\(-\)	17	17	17	17	\(\mathit{minIdx}=2\): nessuno scambio
   3	\(-\)	3	17	17	17	17	\(\mathit{minIdx}:=3\) (\(a[3]=17\))
   	4	3	17	17	17	17	\(a[4]=17\ge a[3]=17\): nessun aggiornamento
   	\(-\)	\(-\)	17	17	17	17	\(\mathit{minIdx}=3\): nessuno scambio

   Array dopo ogni iterazione del ciclo esterno:

   \(i\)	\(\mathit{minIdx}\)	\(a[1]\)	\(a[2]\)	\(a[3]\)	\(a[4]\)	Azione
   \(-\)	\(-\)	17	17	17	17	stato iniziale
   1	1	17	17	17	17	nessuno scambio: \(a[1]=\min(a[1..4])=17\)
   2	2	17	17	17	17	nessuno scambio: \(a[2]=\min(a[2..4])=17\)
   3	3	17	17	17	17	nessuno scambio: \(a[3]=\min(a[3..4])=17\)

   L'algoritmo esegue 6 confronti tra chiavi e 0 scambi, e l'array ordinato è

   \[ [17, 17, 17, 17]. \]