Algoritmo di ordinamento Quick sort in JavaScript

Quick Sort è un algoritmo di ordinamento efficiente basato sul paradigma "divide et impera". Questo metodo utilizza la strategia di dividere il problema in sotto-problemi più piccoli, risolverli separatamente e combinare le soluzioni per ottenere il risultato finale. Esploriamo in dettaglio il funzionamento e l'implementazione di Quick Sort in JavaScript.

L'algoritmo Quick Sort seleziona un elemento come "pivot" e organizza gli altri elementi attorno ad esso, in modo che gli elementi più piccoli del pivot siano alla sua sinistra e gli elementi più grandi siano alla sua destra. Successivamente, l'algoritmo si applica ricorsivamente ai sotto-array a sinistra e a destra del pivot fino a quando l'intero array è ordinato.

Il processo di ordinamento coinvolge i seguenti passaggi:

1. Scegliere un elemento pivot dall'array. Ci sono varie strategie per selezionare il pivot, ma comunemente si sceglie il primo, l'ultimo o l'elemento centrale dell'array.
2. Riorganizzare gli elementi in modo che gli elementi più piccoli del pivot siano a sinistra e gli elementi più grandi siano a destra.
3. Applicare ricorsivamente l'algoritmo ai sotto-array a sinistra e a destra del pivot fino a quando tutti gli elementi sono stati ordinati.

Fonte gif: Wikipedia

Implementazione di Quick Sort in JavaScript

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

function quickSort(arr) {
	if (arr.length <= 1) {
		return arr;
	}

	const pivot = arr[Math.floor(arr.length / 2)];
	const left = [];
	const right = [];

	for (let i = 0; i < arr.length; i++) {
		if (arr[i] < pivot) {
			left.push(arr[i]);
		} else if (arr[i] > pivot) {
			right.push(arr[i]);
		}
	}

	return [...quickSort(left), pivot, ...quickSort(right)];
}

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

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

Complessità Temporale di Quick Sort

Quick Sort ha una complessità temporale media di O(n log n), che lo rende uno degli algoritmi di ordinamento più veloci. Tuttavia, nel caso peggiore (ad esempio, con un pivot scelto in modo subottimale), la complessità può diventare O(n²), rendendo l'algoritmo meno efficiente su dataset particolarmente sfortunati o non bilanciati.

Quick Sort è ampiamente utilizzato in pratica a causa della sua efficienza su dataset mediamente o casualmente disordinati. Tuttavia, è importante selezionare un pivot in modo intelligente per ottenere prestazioni ottimali.

Conclusione

Quick Sort è un algoritmo di ordinamento efficiente e veloce che utilizza una strategia "divide et impera". Sebbene possa soffrire in casi particolari nel caso peggiore, è una scelta eccellente per ordinare grandi dataset in tempi ragionevoli.