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 dell’algoritmo Bubble Sort, 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 Bubble Sort può essere espresso come:

bubbleSort(Arr[], size)
 // loop to access each array element
 for i=0 to size-1 do:
 // loop to compare array elements
 for j=0 to size-i-1 do:
 // compare the adjacent elements
 if Arr[j] > Arr[j+1] then
 // swap them
 swap(Arr[j], Arr[j+1])
 end if
 end for
 end for
 end

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[], size)
 // loop to access each array element
 for i=0 to size-1 do:
 // check if swapping occurs
 swapped = false
 // loop to compare array elements
 for j=0 to size-i-1 do:
 // compare the adjacent elements
 if Arr[j] > Arr[j+1] then
 // swap them
 swap(Arr[j], Arr[j+1])
 swapped = true
 end if
 end for
 // if no elements were swapped that means the array is sorted now, then break the loop.
 if(not swapped) then
 break
 end if
 end for
 end

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.

Correlati: 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:

// C++ implementation of the
 // optimised Bubble Sort algorithm
 #include <iostream>
 using namespace std;
 // Function to perform Bubble Sort
 void bubbleSort(int arr[], int size) {
 // Loop to access each element of the array
 for (int i=0; i<(size-1); i++) {
 // Variable to check if swapping occurs
 bool swapped = false;
 // loop to compare two adjacent elements of the array
 for (int j = 0; j < (size-i-1); j++) {
 // Comparing two adjacent array elements
 if (arr[j] > arr[j + 1]) {
 // Swap both elements if they're
 // not in correct order
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 swapped = true;
 }
 }
 // If no elements were swapped that means the array is sorted now,
 // then break the loop.
 if (swapped == false) {
 break;
 }
 }
 }
 // Prints the elements of the array
 void printArray(int arr[], int size) {
 for (int i = 0; i < size; i++) {
 cout << arr[i] << " ";
 }
 cout << endl;
 }
 int main() {
 int arr[] = {16, 12, 15, 13, 19};
 // Finding the length of the array
 int size = sizeof(arr) / sizeof(arr[0]);
 // Printing the given unsorted array
 cout << "Unsorted Array: " << endl;
 printArray(arr, size);
 // Calling bubbleSort() function
 bubbleSort(arr, size);
 // Printing the sorted array
 cout << "Sorted Array in Ascending Order:" << endl;
 printArray(arr, size);
 return 0;
 }

Produzione:

Unsorted Array:
 16 12 15 13 19
 Sorted Array in Ascending Order:
 12 13 15 16 19

Implementazione Python dell’algoritmo Bubble Sort

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

# Python implementation of the
 # optimised Bubble Sort algorithm
 # Function to perform Bubble Sort
 def bubbleSort(arr, size):
 # Loop to access each element of the list
 for i in range (size-1):
 # Variable to check if swapping occurs
 swapped = False
 # loop to compare two adjacent elements of the list
 for j in range(size-i-1):
 # Comparing two adjacent list elements
 if arr[j] > arr[j+1]:
 temp = arr[j]
 arr[j] = arr[j+1]
 arr[j+1] = temp
 swapped = True
 # If no elements were swapped that means the list is sorted now,
 # then break the loop.
 if swapped == False:
 break
 # Prints the elements of the list
 def printArray(arr):
 for element in arr:
 print(element, end=" ")
 print("")
 arr = [16, 12, 15, 13, 19]
 # Finding the length of the list
 size = len(arr)
 # Printing the given unsorted list
 print("Unsorted List:")
 printArray(arr)
 # Calling bubbleSort() function
 bubbleSort(arr, size)
 # Printing the sorted list
 print("Sorted List in Ascending Order:")
 printArray(arr)

Produzione:

Unsorted List:
 16 12 15 13 19
 Sorted List in Ascending Order:
 12 13 15 16 19

Correlati: Come utilizzare i cicli For in Python

C Implementazione dell’algoritmo Bubble Sort Bubble

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

// C implementation of the
 // optimised Bubble Sort algorithm
 #include <stdio.h>
 #include <stdbool.h>
 // Function to perform Bubble Sort
 void bubbleSort(int arr[], int size) {
 // Loop to access each element of the array
 for (int i=0; i<(size-1); i++) {
 // Variable to check if swapping occurs
 bool swapped = false;
 // loop to compare two adjacent elements of the array
 for (int j = 0; j < (size-i-1); j++) {
 // Comparing two adjacent array elements
 if (arr[j] > arr[j + 1]) {
 // Swap both elements if they're
 // not in correct order
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 swapped = true;
 }
 }
 // If no elements were swapped that means the array is sorted now,
 // then break the loop.
 if (swapped == false) {
 break;
 }
 }
 }
 // Prints the elements of the array
 void printArray(int arr[], int size) {
 for (int i = 0; i < size; i++) {
 printf("%d ", arr[i]);
 }
 printf(" ⁠n ");
 }
 int main() {
 int arr[] = {16, 12, 15, 13, 19};
 // Finding the length of the array
 int size = sizeof(arr) / sizeof(arr[0]);
 // Printing the given unsorted array
 printf("Unsorted Array: ⁠n");
 printArray(arr, size);
 // Calling bubbleSort() function
 bubbleSort(arr, size);
 // Printing the sorted array
 printf("Sorted Array in Ascending Order: ⁠n");
 printArray(arr, size);
 return 0;
 }

Produzione:

Unsorted Array:
 16 12 15 13 19
 Sorted Array in Ascending Order:
 12 13 15 16 19

Implementazione JavaScript dell’algoritmo Bubble Sort Bubble

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

// JavaScript implementation of the
 // optimised Bubble Sort algorithm
 // Function to perform Bubble Sort
 function bubbleSort(arr, size) {
 // Loop to access each element of the array
 for(let i=0; i<size-1; i++) {
 // Variable to check if swapping occurs
 var swapped = false;
 // loop to compare two adjacent elements of the array
 for(let j=0; j<size-i-1; j++) {
 // Comparing two adjacent array elements
 if(arr[j] > arr[j+1]) {
 // Swap both elements if they're
 // not in correct order
 let temp = arr[j];
 arr[j] = arr[j+1];
 arr[j+1] = temp;
 swapped = true;
 }
 // If no elements were swapped that means the array is sorted now,
 // then break the loop.
 if (swapped == false) {
 break;
 }
 }
 }
 }
 // Prints the elements of the array
 function printArray(arr, size) {
 for (let i=0; i<size; i++) {
 document.write(arr[i] + " ");
 }
 document.write("<br>")
 }
 var arr = [16, 12, 15, 13, 19];
 // Finding the length of the array
 var size = arr.length;
 // Printing the given unsorted array
 document.write("Unsorted Array: <br>");
 printArray(arr, size);
 // Calling bubbleSort() function
 bubbleSort(arr, size);
 // Printing the sorted array
 document.write("Sorted Array in Ascending Order: <br>");
 printArray(arr, size);

Produzione:

Unsorted Array:
 16 12 15 13 19
 Sorted Array in Ascending Order:
 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.