Selection sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullata la modifica di 88.55.113.74 (discussione), riportata alla versione precedente di Phantomas Etichetta: Rollback |
|||
(68 versioni intermedie di 44 utenti non mostrate) | |||
Riga 1:
{{Algoritmo
|
|immagine = Sorting selection sort anim.gif
|
|
|
|
|
|
|
}}
L
== 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 31 ⟶ 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
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 ==
Riga 56 ⟶ 89:
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 è il metodo da preferire quando si devono ordinare file costituiti da record estremamente grandi e da chiavi molto piccole. Per queste applicazioni il costo dello spostamento dei dati è prevalente sul costo dei confronti e nessun algoritmo è in grado di ordinare un file con spostamenti di dati sostanzialmente inferiori a quelli dell'ordinamento per selezione.
== Altri progetti ==
{{interprogetto
== Collegamenti esterni ==
* {{Collegamenti esterni}}
{{ordinamento}}
{{portale|informatica}}
[[Categoria:Algoritmi di ordinamento]]
|