Maturità: Ordinamento bubble sort merge

Cos'è l'algoritmo bubble sort?

È un algoritmo di ordinamento che ripete più volte il passaggio attraverso la lista, confrontando elementi adiacenti e scambiandoli se sono nell'ordine sbagliato.

Vero o falso: Bubble sort è efficiente per grandi set di dati.

Falso. Bubble sort ha una complessità temporale di $\displaystyle O(n^2)$, quindi non è efficiente per grandi set di dati.

Qual è l'algoritmo base di bubble sort?

1. Inizia dalla prima posizione. 2. Confronta elementi adiacenti. 3. Scambia se necessario. 4. Ripeti fino a ordinamento completato.

Qual è il caso migliore per bubble sort?

Il caso migliore ha una complessità di $\displaystyle O(n)$, che si verifica quando la lista è già ordinata.

Implementazione: Come si inizia a scrivere bubble sort?

Utilizza un ciclo annidato: il ciclo esterno per passare più volte e il ciclo interno per confrontare e scambiare elementi adiacenti.

Completa: La complessità spaziale di bubble sort è _____.

Costante: $\displaystyle O(1)$, poiché utilizza solo variabili aggiuntive limitate.

Bubble sort è adatto per quali tipi di liste?

Liste piccole o quasi ordinate, dove il costo di esecuzione è accettabile.

Esempio di ordinamento: Lista [5, 3, 8, 4, 2]

[3, 5, 4, 2, 8] → [3, 4, 5, 2, 8] → [2, 3, 4, 5, 8]

Vero o falso: Bubble sort è stabile.

Vero. Bubble sort mantiene l'ordine relativo degli elementi uguali.

Qual è la principale limitazione di bubble sort?

La sua inefficienza su grandi dataset rispetto ad algoritmi più avanzati come quicksort.

Qual è la differenza tra bubble sort e insertion sort?

Bubble sort scambia elementi, mentre insertion sort costruisce una lista ordinata inserendo elementi uno alla volta.

Bubble sort può essere migliorato con la seguente tecnica:

Alcuni algoritmi implementano una flag per terminare l'ordinamento se non ci sono stati scambi nell'ultimo passaggio.

Cos'è l'algoritmo Merge Sort?

Merge Sort è un algoritmo di ordinamento basato sulla tecnica 'divide et impera'. Divide l'array in sottoarray, ordina i sottoarray e poi li unisce.

Qual è la complessità temporale di Merge Sort?

La complessità temporale di Merge Sort è $\displaystyle O(n imes ext{log} n)$ nel caso migliore, peggiore e medio.

Vero o falso: Merge Sort è un algoritmo stabile.

Vero. Merge Sort mantiene l'ordine relativo degli elementi uguali.

Quali sono i passi di Merge Sort?

- Dividere l'array - Ordinare i sottoarray - Unire i sottoarray ordinati

Compila il vuoto: Merge Sort utilizza la strategia _______.

'divide et impera'.

Esempio di Merge Sort: ordina [38, 27, 43, 3, 9, 82, 10].

1. Dividere: [38, 27, 43], [3, 9, 82, 10] 2. Ordinare: [27, 38, 43], [3, 9, 10, 82] 3. Unire: [3, 9, 10, 27, 38, 43, 82].

Cosa fa la funzione di unione in Merge Sort?

La funzione di unione combina due array ordinati in un singolo array ordinato, confrontando gli elementi uno a uno.

Qual è il tipo di approccio di Merge Sort?

Approccio ricorsivo. Ogni chiamata ricorsiva gestisce una porzione dell'array.

Vero o falso: Merge Sort è più veloce di Quick Sort in tutti i casi.

Falso. In media, Quick Sort è più veloce, ma Merge Sort ha un tempo di esecuzione stabile.

Come si gestiscono gli array di lunghezza dispari?

Se l'array ha una lunghezza dispari, uno dei sottoarray avrà un elemento in più durante la divisione.

Qual è lo spazio addizionale richiesto da Merge Sort?

Merge Sort richiede $\displaystyle O(n)$ spazio addizionale per l'array temporaneo utilizzato nell'unione.

Qual è un'applicazione pratica di Merge Sort?

Merge Sort è utilizzato in algoritmi di ordinamento per grandi dataset e in sistemi di gestione di database.