Introduzione all'algoritmo di Bubble Sort

L'ordinamento è una delle operazioni più basilari che puoi applicare ai dati. Puoi ordinare gli elementi in diversi linguaggi di programmazione utilizzando vari algoritmi di ordinamento come Quick Sort, Bubble Sort, Merge Sort, Insertion Sort, ecc. Bubble Sort è l'algoritmo più semplice tra tutti questi.

In questo articolo imparerai a conoscere il funzionamento dell'algoritmo Bubble Sort, lo pseudocodice del Bubble Sort algoritmo, la sua complessità temporale e spaziale e la sua implementazione in vari linguaggi di programmazione come C++, Python, C e JavaScript.

Come funziona l'algoritmo di ordinamento a bolle?

Bubble Sort è l'algoritmo di ordinamento più semplice che scorre ripetutamente l'elenco, confronta gli elementi adiacenti e li scambia se sono nell'ordine sbagliato. Questo concetto può essere spiegato in modo più efficiente con l'aiuto di un esempio. Considera un array non ordinato con i seguenti elementi: {16, 12, 15, 13, 19}.

Esempio:

Qui vengono confrontati gli elementi adiacenti e, se non sono in ordine crescente, vengono scambiati.

Pseudocodice dell'algoritmo Bubble Sort Bubble

In pseudocodice, l'algoritmo di Bubble Sort può essere espresso come:

bubbleSort (Arr[], dimensione)
// loop per accedere a ciascun elemento dell'array
per i=0 alla taglia-1 fai:
// loop per confrontare gli elementi dell'array
per j=0 alla taglia-i-1 fai:
// confronta gli elementi adiacenti
se Arr[j] > Arr[j+1] allora
// scambiali
scambiare (Arr[j], Arr[j+1])
finisci se
fine per
fine per
fine

L'algoritmo di cui sopra elabora tutti i confronti anche se l'array è già ordinato. Può essere ulteriormente ottimizzato interrompendo l'algoritmo se il ciclo interno non ha causato alcuno scambio. Ciò ridurrà il tempo di esecuzione dell'algoritmo.

Pertanto, lo pseudocodice dell'algoritmo ottimizzato di Bubble Sort può essere espresso come:

bubbleSort (Arr[], dimensione)
// loop per accedere a ciascun elemento dell'array
per i=0 alla taglia-1 fai:
// controlla se si verifica lo scambio
scambiato = falso
// loop per confrontare gli elementi dell'array
per j=0 alla taglia-i-1 fai:
// confronta gli elementi adiacenti
se Arr[j] > Arr[j+1] allora
// scambiali
scambiare (Arr[j], Arr[j+1])
scambiato = vero
finisci se
fine per
// se nessun elemento è stato scambiato significa che l'array è ordinato ora, quindi interrompe il ciclo.
se (non scambiato) allora
rompere
finisci se
fine per
fine

Complessità temporale e spazio ausiliario dell'algoritmo di Bubble Sort

La complessità temporale nel caso peggiore dell'algoritmo di Bubble Sort è O(n^2). Si verifica quando l'array è in ordine decrescente e si desidera ordinarlo in ordine crescente o viceversa.

La complessità temporale nel migliore dei casi dell'algoritmo di Bubble Sort è O(n). Si verifica quando l'array è già ordinato.

Relazionato: Che cos'è la notazione Big-O?

La complessità temporale nel caso medio dell'algoritmo Bubble Sort è O(n^2). Si verifica quando gli elementi dell'array sono in ordine confuso.

Lo spazio ausiliario richiesto per l'algoritmo Bubble Sort è O(1).

Implementazione in C++ dell'algoritmo Bubble Sort Bubble

Di seguito è riportata l'implementazione C++ dell'algoritmo Bubble Sort:

// Implementazione C++ di
// Algoritmo di Bubble Sort ottimizzato
#includere 
usando lo spazio dei nomi std;
// Funzione per eseguire Bubble Sort
void bubbleSort (int arr[], int size) {
// Ciclo per accedere a ciascun elemento dell'array
per (int i=0; i// Variabile per verificare se si verifica lo scambio
bool scambiato = falso;
// loop per confrontare due elementi adiacenti dell'array
per (int j = 0; j < (dimensione-i-1); j++) {
// Confronta due elementi dell'array adiacenti
if (arr[j] > arr[j + 1]) {
// Scambia entrambi gli elementi se sono
// non nell'ordine corretto
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temperatura;
scambiato = vero;
}
}
// Se nessun elemento è stato scambiato significa che l'array è ordinato ora,
// quindi interrompe il ciclo.
if (scambiato == falso) {
rompere;
}
}
}
// Stampa gli elementi dell'array
void printArray (int arr[], int size) {
per (int i = 0; io < taglia; io++) {
cout << arr[i] << " ";
}
cout<}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Trovare la lunghezza dell'array
int size = sizeof (arr) / sizeof (arr[0]);
// Stampa l'array non ordinato dato
cout << "Array non ordinato: " << endl;
printArray (arr, dimensione);
// Richiamo della funzione bubbleSort()
bubbleSort (arr, dimensione);
// Stampa l'array ordinato
cout << "Matrice ordinata in ordine crescente:" << endl;
printArray (arr, dimensione);
restituisce 0;
}

Produzione:

Matrice non ordinata: 
16 12 15 13 19 
Array ordinato in ordine crescente:
12 13 15 16 19

Implementazione Python dell'algoritmo Bubble Sort

Di seguito è riportata l'implementazione Python dell'algoritmo Bubble Sort:

# Implementazione Python del
# algoritmo Bubble Sort ottimizzato
# Funzione per eseguire il Bubble Sort
def bubbleSort (arr, size):
# Ciclo per accedere a ogni elemento della lista
per i nell'intervallo (taglia-1):
# Variabile per verificare se si verifica lo scambio
scambiato = falso
# loop per confrontare due elementi adiacenti della lista
per j nell'intervallo (dimensione-i-1):
# Confrontando due elementi di lista adiacenti
se arr[j] > arr[j+1]:
temperatura = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temperatura
scambiato = Vero
# Se nessun elemento è stato scambiato significa che l'elenco è ordinato ora,
# quindi interrompi il ciclo.
se scambiato == Falso:
rompere
# Stampa gli elementi della lista
def printArray (arr):
per elemento in arr:
stampa (elemento, fine = "")
Stampa("")
arr = [16, 12, 15, 13, 19]
# Trovare la lunghezza della lista
dimensione = lente (arr)
# Stampa della lista non ordinata data
print("Elenco non ordinato:")
printArray (arr)
# Richiamo della funzione bubbleSort()
bubbleSort (arr, dimensione)
# Stampa dell'elenco ordinato
print("Lista ordinata in ordine crescente:")
printArray (arr)

Produzione:

Elenco non ordinato:
16 12 15 13 19 
Elenco ordinato in ordine crescente:
12 13 15 16 19

Relazionato: Come usare i cicli For in Python

C Implementazione dell'algoritmo Bubble Sort Bubble

Di seguito è riportata l'implementazione C dell'algoritmo Bubble Sort:

// Implementazione in C di
// Algoritmo di Bubble Sort ottimizzato
#includere 
#includere 
// Funzione per eseguire Bubble Sort
void bubbleSort (int arr[], int size) {
// Ciclo per accedere a ciascun elemento dell'array
per (int i=0; i// Variabile per verificare se si verifica lo scambio
bool scambiato = falso;
// loop per confrontare due elementi adiacenti dell'array
per (int j = 0; j < (dimensione-i-1); j++) {
// Confronta due elementi dell'array adiacenti
if (arr[j] > arr[j + 1]) {
// Scambia entrambi gli elementi se sono
// non nell'ordine corretto
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temperatura;
scambiato = vero;
}
}
// Se nessun elemento è stato scambiato significa che l'array è ordinato ora,
// quindi interrompe il ciclo.
if (scambiato == falso) {
rompere;
}
}
}
// Stampa gli elementi dell'array
void printArray (int arr[], int size) {
per (int i = 0; io < taglia; io++) {
printf("%d", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Trovare la lunghezza dell'array
int size = sizeof (arr) / sizeof (arr[0]);
// Stampa l'array non ordinato dato
printf("Array non ordinato: \⁠n");
printArray (arr, dimensione);
// Richiamo della funzione bubbleSort()
bubbleSort (arr, dimensione);
// Stampa l'array ordinato
printf("Matrice ordinata in ordine crescente: \⁠n");
printArray (arr, dimensione);
restituisce 0;
}

Produzione:

Matrice non ordinata: 
16 12 15 13 19 
Array ordinato in ordine crescente: 
12 13 15 16 19

Implementazione JavaScript dell'algoritmo Bubble Sort Bubble

Di seguito è riportata l'implementazione JavaScript dell'algoritmo Bubble Sort:

// Implementazione JavaScript del
// Algoritmo di Bubble Sort ottimizzato
// Funzione per eseguire Bubble Sort
funzione bubbleSort (arr, size) {
// Ciclo per accedere a ciascun elemento dell'array
per (sia i=0; io// Variabile per verificare se si verifica lo scambio
var scambiato = falso;
// loop per confrontare due elementi adiacenti dell'array
per (sia j=0; j// Confronta due elementi dell'array adiacenti
if (arr[j] > arr[j+1]) {
// Scambia entrambi gli elementi se sono
// non nell'ordine corretto
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temperatura;
scambiato = vero;
}
// Se nessun elemento è stato scambiato significa che l'array è ordinato ora,
// quindi interrompe il ciclo.
if (scambiato == falso) {
rompere;
}
}
}
}
// Stampa gli elementi dell'array
funzione printArray (arr, dimensione) {
per (sia i=0; iodocument.write (arr[i] + " ");
}
documento.write("
")
}
var arr = [16, 12, 15, 13, 19];
// Trovare la lunghezza dell'array
var size = arr.lunghezza;
// Stampa l'array non ordinato dato
document.write("Array non ordinato: 
");
printArray (arr, dimensione);
// Richiamo della funzione bubbleSort()
bubbleSort (arr, dimensione);
// Stampa l'array ordinato
document.write("Array ordinato in ordine crescente: 
");
printArray (arr, dimensione);

Produzione:

Matrice non ordinata:
16 12 15 13 19
Array ordinato in ordine crescente:
12 15 13 16 19

Ora capisci il funzionamento dell'algoritmo di ordinamento a bolle

Bubble Sort è l'algoritmo di ordinamento più semplice ed è utilizzato principalmente per comprendere le basi dell'ordinamento. Bubble Sort può anche essere implementato in modo ricorsivo, ma non offre vantaggi aggiuntivi per farlo.

Usando Python, puoi implementare facilmente l'algoritmo Bubble Sort. Se non hai familiarità con Python e vuoi iniziare il tuo viaggio, iniziare con uno script "Hello World" è un'ottima scelta.

Come iniziare con Python usando uno script "Hello World"

Python è uno dei linguaggi di programmazione più popolari in uso oggi. Segui questo tutorial per iniziare con il tuo primissimo script Python.

Leggi Avanti

Circa l'autore