Selection Sort

7.1 Definizione di Selection Sort

Selection Sort è un algoritmo di ordinamento che trova l'elemento più piccolo dalla parte non ordinata dell'array e lo scambia con il primo elemento di questa parte. Il processo si ripete per gli elementi rimanenti finché l'intero array non è ordinato.

Principio di funzionamento:

1. Iniziamo con il primo elemento dell'array.
2. Troviamo l'elemento più piccolo nella parte non ordinata rimanente dell'array.
3. Scambiamo l'elemento più piccolo con il primo elemento della parte non ordinata.
4. Ripetiamo il processo per l'elemento successivo fino a che l'intero array non sia ordinato.

Processo step-by-step

1. Troviamo l'elemento più piccolo nell'array e lo scambiamo con il primo elemento.
2. Ripetiamo il processo per il resto dell'array (a partire dal secondo elemento).
3. Continuiamo il processo fino a che l'intero array non è ordinato.

Complessità temporale e spaziale del Selection Sort

Complessità temporale:

• Nel peggiore dei casi: O(n^2) — succede quando gli elementi sono ordinati inizialmente in ordine inverso o in modo casuale.
• In media: O(n^2) — si verifica per una disposizione casuale degli elementi.
• Nel migliore dei casi: O(n^2) — anche se l'array è già ordinato, l'algoritmo effettua comunque gli stessi confronti.

Complessità spaziale:

O(1) — poiché l'algoritmo utilizza una quantità costante di memoria aggiuntiva (solo alcune variabili per memorizzare valori temporanei).

7.2 Implementazione dell'algoritmo di Selection Sort

L'implementazione dell'algoritmo è molto semplice:

Step 1: troviamo l'elemento minimo tra tutti gli elementi e lo scambiamo con il primo.

Step 2: troviamo l'elemento minimo tra tutti gli elementi, tranne il primo, e lo scambiamo con il secondo.

Step 3: troviamo l'elemento minimo tra tutti gli elementi, tranne il primo e il secondo, e lo scambiamo con il terzo.

Implementazione in Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Troviamo l'elemento minimo nella parte non ordinata rimanente dell'array
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Scambiamo l'elemento minimo trovato con il primo elemento della parte non ordinata
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Restituiamo l'array ordinato

# Esempio di utilizzo:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Array ordinato:", sorted_arr)
# Output: Array ordinato: [11, 12, 22, 25, 64]

Esempio di funzionamento dell'algoritmo:

1. Primo passaggio (i = 0):
   1. Troviamo l'elemento minimo (11) nella parte non ordinata dell'array [64, 25, 12, 22, 11].
   2. Scambiamo 11 con 64.
   3. Array: [11, 25, 12, 22, 64]
2. Secondo passaggio (i = 1):
   1. Troviamo l'elemento minimo (12) nella parte non ordinata dell'array [25, 12, 22, 64].
   2. Scambiamo 12 con 25.
   3. Array: [11, 12, 25, 22, 64]
3. Terzo passaggio (i = 2):
   1. Troviamo l'elemento minimo (22) nella parte non ordinata dell'array [25, 22, 64].
   2. Scambiamo 22 con 25.
   3. Array: [11, 12, 22, 25, 64]
4. Quarto passaggio (i = 3):
   1. Troviamo l'elemento minimo (25) nella parte non ordinata dell'array [25, 64].
   2. 25 è già al suo posto, nessuno scambio necessario.
   3. Array: [11, 12, 22, 25, 64]

L'algoritmo termina poiché tutti gli elementi sono ordinati.