Confronti
Scambi
Passata

  • Confrontate
  • Minimo finora
  • Scambiate
  • Al loro posto

Scopri di più sul selection sort

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

  1. Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
  2. 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.
  3. 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