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
|classclasse = [[Algoritmo di ordinamento]]
|immagine = Sorting selection sort anim.gif
|image=[[File:Selection sort animation.gif|none|288px|Animazione dell'algoritmo che ordina dei numeri casuali]]
|captiondidascalia = Animazione dell'algoritmo che ordina dei numeri casuali
|datastruttura dati = [[Array]]
|timetempo = ''O(n²)''
|best-timetempo migliore = ''O(n²)''
|average-timetempo medio = ''O(n²)''
|spacespazio = ''O(n)'' totale<br />''O(1)'' ausiliario
|optimalottimale = No
}}
L<nowiki>{{'</nowiki>}}'''ordinamento per selezione''' ('''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 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 -+ 1) + 1 ) = \sum_{i=1}^{n-1} (n -i) = \sum_{i=1)}^{n-1} n - \sum_{i=1}^{n-1} i \approx n^2(n-1) - \frac{n(n +- 1)}{2} \approx \frac{n^2}{2} = \theta(n^2) </math>
 
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'');
<code>
'''for''' i = 10 '''to''' n - 1
'''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
aus'''if''' posmin != a[i]
a[i] tmp ← a[posmini]
a[posmini] ← ausa[posmin]
a[posmin] ← tmp
</code>
 
==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.
 
Una variante del selection sort più efficiente si ottiene usando un vettore di appoggio e riducendo l'array da ordinare, in questo modo ad ogni iterazione si riduce il tempo di calcolo.[http://porteardenti.blogspot.it/2013/04/java-ordinamento-di-un-array.html]
 
== Altri progetti ==
{{interprogetto|commons=Category:Selection sort|b=Implementazioni di algoritmi/Selection sort|b_oggetto=implementazioni|b_preposizione=didel|preposizione=sul}}
 
== Collegamenti esterni ==
* {{Collegamenti esterni}}
 
{{ordinamento}}
{{portale|informatica}}
 
[[Categoria:Algoritmi di ordinamento]]