Selection Sort

1. Cos'è il Selection Sort?

Il Selection Sort (ordinamento per selezione) è un algoritmo iterativo elementare che organizza una sequenza dividendola idealmente in due parti: una sotto-sequenza sinistra già ordinata e una sotto-sequenza destra non ordinata.

Ad ogni iterazione, l'algoritmo analizza la porzione non ordinata alla ricerca dell'elemento con valore minimo. Una volta individuato, lo scambia con il primo elemento disponibile della parte non ordinata, espandendo così i confini della zona ordinata di un elemento.

2. Meccanismo di Funzionamento

L'algoritmo esegue un ciclo esterno che scorre l'array dalla prima posizione fino alla penultima ($N-1$ passate). All'interno, un ciclo secondario esplora gli elementi rimanenti per identificare l'indice del valore minimo assoluto di quella specifica porzione.

                // Implementazione del Selection Sort in C++
                #include <vector>
                #include <algorithm>
                #include <iostream>

                void selectionSort(std::vector<int>& v) {
                int n = v.size();

                for (int i = 0; i < n - 1;
                i++) {
                int minIndex = i;
                for (int j = i + 1; j < n;
                j++) {
                if (v[j] < v[minIndex]) {
                minIndex = j;
                }
                }
                // Scambia il minimo trovato con il primo elemento non ordinato
                if (minIndex != i) {
                std::swap(v[i], v[minIndex]);
                }
                }
                }
            

3. Analisi della Complessità

Complessità Temporale $\mathcal{O}(N^2)$ (Tutti i casi): A differenza di altri algoritmi, il Selection Sort esegue lo stesso numero di confronti indipendentemente dallo stato iniziale del vettore (anche se è già ordinato). Il numero totale di confronti è dato dalla formula $\frac{N(N-1)}{2}$.
Complessità Spaziale $\mathcal{O}(1)$: L'algoritmo opera in-place, richiedendo una quantità costante di memoria aggiuntiva per le variabili di supporto.

4. Simulatore Interattivo: Esecuzione Selection Sort

Inserisci una sequenza di numeri interi separati da virgola per testare l'ordinamento per selezione e verificare i passaggi e i confronti eseguiti.

selection-sort@nexus-core:~# Selection Sort Simulator

Vettore Numerico (separato da virgole):

> Configura il vettore numerico per avviare la simulazione interattiva del Selection Sort.

1. Cos'è il Selection Sort?

2. Meccanismo di Funzionamento

3. Analisi della Complessità

4. Simulatore Interattivo: Esecuzione Selection Sort

Gestione della Privacy e dei Cookie