Esistono diversi algoritmi di ordinamento. Ora devi trovare l’algoritmo di ordinamento più veloce. Guarda il programma Scratch e sperimentalo. Qual è l’algoritmo di ordinamento più veloce? È il più veloce indipendentemente dalla lunghezza dell’elenco?
Prova gli algoritmi di ordinamento con un elenco molto piccolo (meno di 100 elementi). Ci sono differenze tra gli algoritmi di ordinamento?
Nota: questo esercizio è stato creato in modo tale da poter essere utilizzato anche in lezioni con alunni più grandi.
Introduzione
Premi la bandiera verde per avviare il programma. Quindi premi uno degli algoritmi di ordinamento a destra. Non appena il pulsante diventa rosso, l’algoritmo di ordinamento è terminato.
Se si desidera utilizzare un altro algoritmo di ordinamento, è necessario creare un nuovo elenco. Per farlo, premi “Nuovo elenco”.
In basso a sinistra è possibile modificare la lunghezza dell’elenco, ma è necessario premere prima “Nuovo elenco” per avere un elenco della lunghezza desiderata.
Esempio di soluzione
Normalmente, l’ordinamento rapido è il più veloce dei tre algoritmi di ordinamento. Se i dati sono pochi, i tre algoritmi di ordinamento sono altrettanto veloci.
Aggiunta
Per questo compito utilizza nuovamente il programma utilizzato sopra.
Se vuoi, puoi anche osservare gli algoritmi di ordinamento al lavoro. Riesci a capire come funzionano? Suggerimento: qual è il ruolo della barra rossa? Qual è il ruolo della barra gialla?
Attenzione: se il programma deve generare anche un grafico, non è più possibile confrontare la velocità degli algoritmi.
Esempio di soluzione
La barra rossa rappresenta il valore attualmente selezionato. Viene confrontato con il valore giallo.
La differenza tra i diversi algoritmi di ordinamento è la selezione dei due valori.
Con l’ordinamento a bolle, il valore selezionato viene confrontato con il valore successivo. Se il valore successivo è più piccolo, la posizione viene modificata. Se è più grande, il valore più grande diventa il valore selezionato.
Con l’ordinamento a inserzione, il valore selezionato viene confrontato in sequenza con tutti i valori ordinati in precedenza. Non appena viene trovata la posizione corrispondente, il valore vi rimane.
Con l’ordinamento rapido, viene selezionato prima un valore di confronto (perno). L’ordinamento rapido funziona meglio quando il perno si trova al centro dell’intervallo di valori. Quindi i valori su entrambi i lati vengono confrontati con il perno. Tutti i valori più grandi del perno vengono spostati su un lato. Tutti i valori più piccoli vengono spostati dall’altra parte. Quindi si determina nuovamente un perno su ciascuno dei due lati e si applica nuovamente la procedura.