Algoritmo di ordinamento Bubble sort in JavaScript

Bubble Sort è uno degli algoritmi di ordinamento più semplici ed è comunemente utilizzato per ordinare una serie di elementi in un array. Questo algoritmo confronta ripetutamente coppie di elementi adiacenti e li scambia se sono disordinati, muovendo gradualmente gli elementi più grandi verso la fine dell'array. Esploriamo in dettaglio il funzionamento e l'implementazione di Bubble Sort in JavaScript.

Bubble Sort prende il nome dal modo in cui gli elementi più grandi "salgono" gradualmente verso la fine dell'array, come le bolle in un bicchiere d'acqua. Il processo di ordinamento coinvolge i seguenti passaggi:

• Si parte dall'inizio dell'array e si confrontano gli elementi adiacenti.
• Se l'elemento successivo è più piccolo dell'elemento corrente, avviene uno scambio.
• Questo processo continua fino a quando non si raggiunge la fine dell'array. Questo passaggio assicura che l'elemento più grande sia spostato verso la fine dell'array.
• Si ripete il processo per tutti gli elementi dell'array, continuando a scambiare coppie disordinate fino a quando l'intero array è ordinato.

Fonte gif: Wikipedia

Implementazione di Bubble Sort in JavaScript

Ecco un'implementazione base di Bubble Sort in JavaScript:

function bubbleSort(arr) {
	const len = arr.length;
	for (let i = 0; i < len - 1; i++) {
		for (let j = 0; j < len - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				// Scambio gli elementi disordinati
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
			}
		}
	}
	return arr;
}

Questo codice definisce una funzione bubbleSort che accetta un array come argomento e lo ordina utilizzando l'algoritmo Bubble Sort. Per utilizzare tale funzione dobbiamo quindi definire un array di numeri e passarlo alla funzione bubbleSort.

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

Complessità Temporale di Bubble Sort

Bubble Sort è noto per la sua semplicità, ma è anche un algoritmo inefficiente, specialmente su array di grandi dimensioni. La sua complessità temporale è di O(n^2) nel caso peggiore e nel caso medio, rendendolo poco efficiente per grandi quantità di dati.

Bubble Sort è utile principalmente per scopi educativi o in situazioni in cui la quantità di dati è limitata e non eccessivamente grande. È meno adatto per utilizzi pratici in applicazioni dove le prestazioni sono cruciali, a causa della sua lentezza su grandi dataset.

Ottimizzazione: Bubble sort con sentinella

L'ottimizzazione dell’algoritmo di ordinamento Bubble Sort tramite l'implementazione con sentinella mira a ridurre il numero di confronti necessari. Aggiungendo un'ottimizzazione che utilizza una variabile sentinella, si può interrompere il ciclo se durante una passata non ci sono scambi, poiché questo significa che l'array è già ordinato. Ecco un'esemplificazione di questa ottimizzazione all'algoritmo Bubble Sort in JavaScript:

function bubbleSortSentinella(arr) {
	const len = arr.length;
	let scambi;
	
	for (let i = 0; i < len - 1; i++) {
		scambi = false;
		
		for (let j = 0; j < len - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
				scambi = true;
			}
		}

		// Se durante una passata non ci sono stati scambi, l'array è ordinato
		if (!scambi) {
			break;
		}
	}
	
	return arr;
}

Questa versione aggiunge la variabile 'scambi' per tracciare se è avvenuto uno scambio durante una singola passata. Se non ci sono stati scambi, l'algoritmo interrompe l'esecuzione poiché l'array è già ordinato. Questa ottimizzazione riduce il numero di confronti nei casi in cui l'array è già ordinato o si avvicina all'essere ordinato, migliorando leggermente le prestazioni dell'algoritmo.

L'implementazione ottimizzata con la sentinella migliora le prestazioni del Bubble Sort in situazioni in cui l'array è parzialmente ordinato o già completamente ordinato, riducendo il numero di iterazioni necessarie per completare l'ordinamento. Va notato che, nonostante l'ottimizzazione, la complessità temporale nel caso peggiore e nel caso medio rimane O(n²), rendendo Bubble Sort inadatto per grandi dataset.

Conclusione

Bubble Sort è un algoritmo semplice e facile da comprendere, ma la sua efficienza diminuisce su dataset più grandi. Nonostante la sua limitata applicazione pratica, è un ottimo modo per introdurre i concetti di ordinamento agli studenti di informatica e per comprendere i principi di base degli algoritmi di ordinamento.