Algoritmi ricorsivi per l'ordinamento

Algoritmi ricorsivi per l'ordinamento

Alcuni degli algoritmi più efficienti e semplici fanno utilizzo della tecnica ricorsiva per ridurre la complessità dell’algoritmo stesso.
Tra questi due tra i più importanti in letteratura sono l’algoritmo Merge Sort e l’algoritmo Quick Sort.

• Merge Sort: il suo funzionamento consiste nel dividere ricorsivamente il vettore in due parti, sinistra e destra, fino a raggiungere dei vettori di dimensione unitaria per poi riunire in post order ordinando i sotto-vettori (visivamente si forma un albero di ricorsione del vettore da ordinare); algoritmo di ordinamento stabile non in loco di complessità O(n log(n));
• Quick Sort: consiste nell’ordinamento del vettore basandosi su un pivot scelto secondo un metodo deciso in partenza (il primo elemento, l’ultimo o uno qualsiasi tra gli altri); tramite due indici si scorre quindi il vettore e si cercano a sinistra il primo elemento maggiore del pivot e a destra il primo elemento minore del pivot scambiandoli ogni volta che vengono trovati entrambi e continuando così finchè i due indici non si scavalcano, a quel punto si scambia l’elemento con indice l’indice che in partenza era sulla sinistra con il pivot; si ricorre quindi sui due sotto-vettori destro e sinistro in base al pivot, esso stesso escluso dai sottovettori, si ripete quindi il procedimento fino a dimensione unitaria dei sottovettori; algoritmo di ordinamento in loco non stabile di complessita O(n^2).