Quali tipi di ordinamento conosci e quali sono le loro difficoltà in termini di tempo e memoria?

Esistono molti algoritmi di ordinamento, ecco i principali con la loro complessità temporale e spaziale:

• Bubble Sort (Ordinamento a bolle)

  • Tempo: O(n²) nel peggiore e medio caso
  • Memoria: O(1) (ordinamento in loco)

• Insertion Sort (Ordinamento per inserimento)

  • Tempo: O(n²) nel peggiore, O(n) nel migliore (array quasi ordinato)
  • Memoria: O(1)

• Selection Sort (Ordinamento per selezione)

  • Tempo: O(n²) in tutti i casi
  • Memoria: O(1)

• Merge Sort (Ordinamento per fusione)

  • Tempo: O(n log n) in tutti i casi
  • Memoria: O(n) (richiede memoria aggiuntiva per la fusione)

• Quick Sort (Ordinamento rapido)

  • Tempo: O(n log n) in media, O(n²) nel peggiore (raro)
  • Memoria: O(log n) (pila ricorsiva)

• Heap Sort (Ordinamento con heap)

  • Tempo: O(n log n) in tutti i casi
  • Memoria: O(1)

• Timsort — algoritmo di ordinamento ibrido usato in Python e Java

  • Tempo: O(n log n) in media e nel peggiore
  • Memoria: O(n)

La scelta dell'algoritmo dipende dalla dimensione dei dati, dai requisiti di memoria e dalla stabilità dell'ordinamento (se mantiene l'ordine degli elementi uguali). Ad esempio, Merge Sort è stabile, Quick Sort è generalmente più veloce, ma instabile.