Informazioni su questo esperimento
Osserva come bubble sort, insertion sort e merge sort trasformano lo stesso input in ordine crescente. Metti in pausa durante un confronto, procedi passo dopo passo per ogni scrittura oppure torna indietro lungo l’intera traccia. I conteggi separati dei confronti tra valori e delle scritture nell’array principale aiutano a distinguere il lavoro dell’algoritmo dalla durata dell’animazione.
Obiettivi di apprendimento
- Tracciare confronti e scritture in tre algoritmi di ordinamento per confronto
- Confrontare le prestazioni con input mescolati, ordinati e invertiti
- Distinguere la crescita quadratica nel caso peggiore dalla crescita n log n
Come si usa
- 1Mantieni invariati l’input mescolato e la lunghezza dell’array. Completa bubble sort e annota i confronti e le scritture.
- 2Riavvia con insertion sort e poi con merge sort, usando lo stesso input. Confronta i conteggi finali.
- 3Prova un input ordinato e osserva l’uscita anticipata di bubble sort e i pochi confronti di insertion sort.
- 4Usa «Precedente» e il cursore della traccia per esaminare una fusione. I buffer temporanei possono contenere valori che non sono più visibili nelle loro posizioni originali nell’array principale.
Il modello
Ipotesi
- Gli input contengono numeri interi univoci da 1 a n. Il mescolamento usa un seed fisso, così ogni algoritmo riceve dati identici.
- Un confronto è un test tra valori dei dati, non un test di indice o di limite del ciclo. Una scrittura è un’assegnazione nell’array principale, inclusa la chiave di inserimento anche quando non cambia.
- Le copie nei buffer temporanei di merge sort non vengono incluse nel conteggio delle scritture. L’uso di memoria aggiuntiva non è incluso nei totali delle operazioni visualizzati.
- La velocità di riproduzione è scelta a fini didattici e non è un benchmark delle prestazioni in tempo reale.
Provalo in classe
- Q1Perché in questa implementazione bubble sort richiede solo n − 1 confronti quando l’input è già ordinato?
- Q2Quale algoritmo esegue meno confronti con un input in ordine inverso e un array della stessa lunghezza?
- Q3Perché il numero di fotogrammi dell’animazione non è una misura affidabile della velocità di un algoritmo?
Domande frequenti
Perché i valori sembrano duplicarsi brevemente durante l’ordinamento per inserimento o per fusione?
Un valore può essere conservato temporaneamente in una chiave o in un buffer di fusione mentre l’array principale viene sovrascritto. La visualizzazione mostra il contenuto dell’array principale a ogni scrittura; l’unicità viene ripristinata al termine dell’operazione.
L’ordinamento per fusione usa sempre meno scritture?
No. L’ordinamento per fusione ha una crescita efficiente del numero di confronti, ma riscrive ripetutamente i risultati della fusione. Il conteggio delle operazioni dipende dall’input e da quali assegnazioni vengono conteggiate esattamente.