Selection sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica Etichette: Possibili insulti diretti o linguaggio triviale Possibile attacco personale o turpiloquio Modifica visuale Modifica da mobile Modifica da web per mobile |
m Annullata la modifica di 88.55.113.74 (discussione), riportata alla versione precedente di Phantomas Etichetta: Rollback |
||
(54 versioni intermedie di 33 utenti non mostrate) | |||
Riga 1:
{{Algoritmo
|
|
|
|
|
|
|
|
|
}}
L{{'}}''
▲'''e''' ('''selection sort''') è un [[algoritmo di ordinamento]] che opera [[Algoritmo in loco|in place]] ed in modo simile all'[[insertion sort|ordinamento per inserzione]]. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.
== Descrizione dell'algoritmo ==
L'algoritmo ''seleziona'' di volta in volta il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sottosequenza ordinata, che occupa le prime posizioni dell'array, e la sottosequenza ''da'' ordinare, che costituisce la parte restante dell'array.
{|
|
Riga 33 ⟶ 30:
<math>\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} c </math>, dove ''c'' è una costante, dato che l'operazione effettuata può essere rappresentata da una costante.
<math>\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \sum_{i=1}^{n-1} (n - (i + 1) + 1 ) = \sum_{i=1}^{n-1}(n-i) = \sum_{i=1}^{n-1} n - \sum_{i=1}^{n-1} i \approx n(n-1) - \frac{n(n
L'ordinamento per selezione effettua <math>N(N-1)/2</math> confronti e, nel caso peggiore/migliore/medio, <math>\theta(n-1)</math> scambi.
La complessità di tale algoritmo è dell'ordine di <math>\theta(n^2).</math>
==Pseudocodice==
Quella che segue è una rappresentazione in [[pseudocodice]] del Selection sort:
▲ '''procedure''' SelectionSort(a: ''lista dei numeri da ordinare'');
▲ '''for''' i = 1 '''to''' n - 1
posmin ← i
'''for''' j = (i + 1) '''to''' n
'''if''' a[j] < a[posmin]
posmin ← j
a[
a[posmin] ← tmp
==Implementazioni==
Di seguito una possibile implementazione in [[Java (linguaggio di programmazione)|Java]] :
<syntaxhighlight lang="java" line="1">
class SelectionSort{
public static void sort(int arr[]){
// Lunghezza array
int n=arr.length;
// Incrementa di 1 il limite inferiore del sub array da ordinare
for (int i = 0; i < n-1; i++)
{
// Trova il minimo nel subarray da ordinare
int indice_min = i;
for (int j = i+1; j < n; j++) {
// Confronto per trovare un nuovo minimo
if (arr[j] < arr[indice_min])
indice_min = j; // Salvo l'indice del nuovo minimo
}
// Scambia il minimo trovato con il primo elemento
swap(arr,indice_min,i);
}
}
private static void swap(int[] arr, int a , int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
</syntaxhighlight>
== Casi limite ==
Un inconveniente dell'algoritmo di ordinamento per selezione è che il tempo di esecuzione dipende solo in modo modesto dal grado di ordinamento in cui si trova il file. La ricerca del minimo elemento durante una scansione del file non sembra dare informazioni circa la posizione del prossimo minimo nella scansione successiva. Chi utilizza questo algoritmo potrebbe stupirsi nel verificare che esso impiega più o meno lo stesso tempo sia su file già ordinati che su file con tutte le chiavi uguali, o anche su file ordinati in modo casuale.
Nonostante l'approccio ''brutale'' adottato, l'ordinamento per selezione ha un'importante applicazione: poiché ciascun elemento viene spostato al più una volta, questo tipo di ordinamento
== Altri progetti ==
{{interprogetto
== Collegamenti esterni ==
* {{Collegamenti esterni}}
{{ordinamento}}
{{portale|informatica}}
[[Categoria:Algoritmi di ordinamento]]
|