Complessità temporale e spaziale

Complessità temporale:

• Caso migliore, medio e peggiore: O(n²)
  • Selection Sort scansiona sempre l’intera parte non ordinata per trovare il minimo, anche se l’array è già ordinato. Il numero di confronti non dipende dall’ordine dei dati in input.

Complessità spaziale:

• O(1)
  • Selection Sort è un algoritmo «in-place». Riordina gli elementi utilizzando solo una quantità costante di memoria aggiuntiva, indipendentemente dalle dimensioni dell’input.

Riepilogo:

• Selection Sort è semplice ed efficiente in termini di memoria.
• Effettua pochi scambi (al massimo n-1), caratteristica utile quando le operazioni di scrittura sono costose.
• La sua complessità temporale quadratica lo rende una scelta poco adatta per grandi insiemi di dati, per i quali sono preferibili algoritmi come Merge Sort o Quick Sort.