Selection sort

Il selection sort fa parte degli algoritmi di sorting, ed è una procedura ricorsiva. $\in O(n^2)$

Input Sequenza di $n$ valori $A=<a_0,a_1,...,a_{n-1}>$.

Output Permutazione $<a_0^{\prime },a_1^{\prime },...,a_{n-1}^{\prime }>$ della sequenza $A$ tale che $a_0^{\prime }\le a_1^{\prime }\le ...\le a_{n-1}^{\prime }$

title: Attenzione
Come costo computazionale calcoliamo i confronti eseguiti tra i valori di A.

1. Cerca il valore minimo tra gli $n$ elementi e lo scambia con quello al primo posto
2. Ordina i restanti $n-1$ elementi allo stesso modo
3. Quando rimane solo in elemento da riordinare, la procedura termina

SelectionSort(A, i, j):
	if i == j then
		return
	else
		k := IndexForMin(A, i, j)
		inverti A[i] e A[k]
		SelectionSort(A, i+1, j)

Chiamata principale: SelectionSort(a, 0, n-1).

Funzione per trovare l’indice dell’elemento minore nell’array:

IndexForMin(A, i, j):
	k := i
	for l = i + 1 to j:
		if A[l] < A[k] then
			k := l
	return k

Il costo computazionale di IndexForMin è esattamente $n-1-i-1$, il che rientra in $\Theta (n-i)$.

Calcolo del costo dell’algoritmo:

• caso base: $i=j$
• ogni chiamata ricorsiva richiede i confronti tra gli elementi per trovare $k$, + quelli della chiamata successiva
• dato A con i e j, IndexForMin richiede $n-1-i-1$ operazioni
• la procedura ricorsiva viene invocata 1 volta per ogni i tale che $0\le i\le n-2$

Questo si trasforma in

$$\begin{array}{rl}T(n)=\sum _{i=0}^{n-2}(n-1-i-1)& =(n-2)-\sum _{i=0}^{n-2}i\\ & =(n-2)-\sum _{i=0}^{n-2}1-\frac{(n-2)(n-1)}{2}\\ & =(n-2)(n-1)-\frac{(n-2)(n-1)}{2}\\ & \in \Theta (n^2)\end{array}$$

asd_11