Selection sort
Selection sort | |
---|---|
![]() | |
Classe | Algoritmo di ordinamento |
Struttura dati | Array |
Caso peggiore temporalmente | O(n²) |
Caso ottimo temporalmente | O(n²) |
Caso medio temporalmente | O(n²) |
Caso peggiore spazialmente | O(n) totale O(1) ausiliario |
Ottimale | No |
Manuale |
L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in place ed in modo simile all'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.
Dovendo ordinare un array A di lunghezza n, si fa scorrere l'indice i da 1 a n-1 ripetendo i seguenti passi:
| ![]() |
Analisi delle prestazioni
Il ciclo interno è un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo è determinato dal numero di confronti.
A livello asintotico viene studiato il tempo di esecuzione dei due cicli for.
, dove c è una costante, dato che l'operazione effettuata può essere rappresentata da una costante.
L'ordinamento per selezione effettua confronti e, nel caso peggiore/migliore/medio, scambi.
La complessità di tale algoritmo è dell'ordine di
Pseudocodice
Quella che segue è una rappresentazione in pseudocodice del Selection sort:
procedure SelectionSort(a: lista dei numeri da ordinare); for i = 0 to n - 1 posmin ← i for j = (i + 1) to n if a[j] < a[posmin] posmin ← j if posmin != i tmp ← a[i] a[i] ← a[posmin] a[posmin] ← tmp
Implementazioni
Di seguito una possibile implementazione in Java :
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; } }
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 è 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
Altri progetti
- Wikibooks
- Wikimedia Commons
Wikibooks contiene implementazioni del selection sort
Wikimedia Commons contiene immagini o altri file sul selection sort
Collegamenti esterni
- (EN) Eric W. Weisstein, Selection sort, su MathWorld, Wolfram Research.
V · D · M | ||
---|---|---|
Teoria | Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo | ![]() |
Algoritmi a scambio | Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort | |
Algoritmi di selezione | Selection sort · Heap sort · Smoothsort | |
Algoritmi ad inserimento | Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting | |
Algoritmi a fusione | Merge sort · Timsort | |
Algoritmi non comparativi | Radix sort · Bucket sort · Counting sort · Pigeonhole sort | |
Altri algoritmi | Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle | |
Algoritmi inefficienti | Stupid sort · Trippel sort |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)