Quick Sort

1. Cos'è il Quick Sort?

Il Quick Sort è uno degli algoritmi di ordinamento più veloci ed utilizzati in informatica. Sfrutta anch'esso il paradigma del Divide et Impera, ma con un approccio differente rispetto al Merge Sort: sceglie un elemento di riferimento chiamato pivot e partiziona il vettore in modo tale che tutti gli elementi minori del pivot vengano posizionati a sinistra, mentre quelli maggiori a destra.

Una volta completata la fase di partizionamento, il pivot si trova nella sua posizione definitiva all'interno dell'array ordinato. L'algoritmo viene quindi richiamato ricorsivamente sulle due sotto-sezioni sinistra e destra.

2. Meccanismo di Funzionamento e Codice C++

La logica si articola attorno alla funzione di partizionamento (schema di Lomuto o Hoare), che riorganizza gli elementi attorno al pivot scelto e restituisce l'indice della sua collocazione finale.

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

                int partition(std::vector<int>& v, int low, int high) {
                int pivot = v[high];
                int i = (low - 1);

                for (int j = low; j <= high
                - 1; j++) {
                if (v[j] <= pivot) {
                i++;
                std::swap(v[i], v[j]);
                }
                }
                std::swap(v[i + 1], v[high]);
                return (i + 1);
                }

                void quickSort(std::vector<int>& v, int low, int high) {
                if (low < high) {
                int pi = partition(v, low, high);
                quickSort(v, low, pi - 1);
                quickSort(v, pi + 1, high);
                }
                }
            

3. Analisi della Complessità

Complessità Temporale nel Caso Medio $\mathcal{O}(N \log N)$: Si verifica quando il partizionamento divide il vettore in parti circa uguali, garantendo prestazioni ottimali.
Complessità Temporale nel Caso Peggiore $\mathcal{O}(N^2)$: Si verifica se la scelta del pivot risulta sistematicamente sfavorevole (ad esempio scegliendo sempre il valore minimo o massimo in un array già ordinato).
Complessità Spaziale $\mathcal{O}(\log N)$: Richiede memoria sullo stack di sistema proporzionale alla profondità della ricorsione.

4. Simulatore Interattivo: Esecuzione Quick Sort

Inserisci una sequenza di numeri interi separati da virgola per testare l'ordinamento rapido e verificare le metriche di esecuzione.

quick-sort@nexus-core:~# Quick Sort Simulator

Vettore Numerico (separato da virgole):

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

1. Cos'è il Quick Sort?

2. Meccanismo di Funzionamento e Codice C++

3. Analisi della Complessità

4. Simulatore Interattivo: Esecuzione Quick Sort

Gestione della Privacy e dei Cookie