- Confrontate
- Minimo finora
- Scambiate
- Al loro posto
Selection sort
Il selection sort costruisce la lista ordinata partendo dall'inizio. Ogni passata scorre i valori non ancora ordinati, tiene traccia del più piccolo e lo porta con uno scambio nella prima posizione non ordinata. Avvia l'ordinamento a qualsiasi velocità, oppure procedi un confronto alla volta, e guarda i contatori di confronti, scambi e passate. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. I riquadri contano confronti, scambi e passate. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
- Premi Avvia, oppure usa Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
- Guarda come cambia il valore più piccolo finora durante la scansione, e lo scambio che lo mette al suo posto alla fine di ogni passata.
Come funziona il selection sort
Guarda ogni valore della lista e ricorda il più piccolo. Scambialo con il primo valore: la prima posizione ora è definitiva. Poi fai lo stesso con il resto della lista, partendo una posizione più avanti. Dopo n − 1 passate ogni valore è al suo posto, e l'ultimo lo è di conseguenza.
Molti confronti, pochi scambi
La scansione non si ferma mai prima, perché solo dopo aver guardato tutti i valori rimasti può sapere con certezza qual è il più piccolo. Così il selection sort fa esattamente n(n − 1)/2 confronti per n valori, che la lista sia ordinata, inversa o casuale. In cambio fa al massimo n − 1 scambi, uno per passata. Per questo è una scelta sensata quando spostare un valore costa molto più che confrontarne due.
Domande frequenti
Come funziona il selection sort?
Seleziona ripetutamente il valore più piccolo non ancora ordinato e lo porta con uno scambio nella prima posizione non ordinata. Dopo la passata k le prime k posizioni contengono i k valori più piccoli in ordine.
Quanti confronti e scambi fa il selection sort?
Sempre n(n − 1)/2 confronti per n valori: 45 per 10 valori, 780 per 40. Gli scambi sono al massimo n − 1, uno per passata, e meno quando il valore più piccolo è già al suo posto.
Perché una lista ordinata richiede tanto tempo quanto una inversa?
Perché ogni passata deve guardare tutti i valori rimasti per essere sicura di aver trovato il più piccolo. A differenza del bubble sort e dell'insertion sort, il selection sort non può capire dai suoi confronti che la lista è già ordinata.
Il selection sort è stabile?
Non in questa forma comune. Uno scambio può portare un valore oltre un valore uguale: in 2, 2, 1 il primo 2 si scambia con l'1 e finisce dietro il secondo 2. Una versione che sposta i valori invece di scambiarli è stabile, al costo di più spostamenti.
I miei numeri vengono inviati da qualche parte?
No. L'ordinamento avviene nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor