Algoritmo di ordinamento Selection sort in JavaScript

Selection Sort è un semplice algoritmo di ordinamento che seleziona ripetutamente l'elemento più piccolo dall'array e lo inserisce nella posizione corretta. Questo metodo è intuitivo ma non efficiente per grandi dataset. Esploriamo in dettaglio il funzionamento e l'implementazione di Selection Sort in JavaScript.

L'algoritmo Selection Sort divide l'array in due parti: una parte ordinata e una parte non ordinata. Durante ogni passaggio, cerca l'elemento più piccolo nella parte non ordinata e lo scambia con il primo elemento della parte non ordinata, espandendo così la sezione ordinata.

Il processo di ordinamento coinvolge i seguenti passaggi:

1. Si itera attraverso l'intero array, cercando l'elemento più piccolo nella parte non ordinata.
2. Si scambia l'elemento più piccolo con il primo elemento della parte non ordinata, rendendo così il primo elemento parte della sezione ordinata.
3. Si espande la sezione ordinata muovendo l'indice di inizio della parte non ordinata verso destra.

Fonte gif: Wikipedia

Implementazione di Selection Sort in JavaScript

Ecco un'implementazione di base di Selection Sort in JavaScript:

function selectionSort(arr) {
	const len = arr.length;
	
	for (let i = 0; i < len - 1; i++) {
		let minIndex = i;

		for (let j = i + 1; j < len; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}

		if (minIndex !== i) {
			[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
		}
	}

	return arr;
}

Questa implementazione definisce una funzione selectionSort che accetta un array come argomento e lo ordina utilizzando l'algoritmo Selection Sort.

let array = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(array)); // Output: [11, 12, 22, 25, 34, 64, 90]

Complessità Temporale di Selection Sort

Selection Sort ha una complessità temporale di O(n²) nel caso peggiore e nel caso medio, il che lo rende inefficiente per grandi dataset. Anche se è semplice da implementare, altri algoritmi come Merge Sort o Quick Sort sono più efficienti per grandi quantità di dati.

Selection Sort è utile principalmente per scopi educativi o in situazioni in cui si tratta di piccoli dataset, in quanto la sua complessità rende inefficiente il suo utilizzo su dataset più grandi. Può essere utile per piccole liste o come passaggio iniziale per un algoritmo più efficiente su dataset parzialmente ordinati.

Conclusione

Selection Sort è un algoritmo intuitivo ma non ottimale per grandi dataset a causa della sua complessità O(n²). Sebbene possa essere utile in alcune situazioni specifiche, altri algoritmi di ordinamento sono generalmente preferiti per la loro maggiore efficienza.