Algoritmo di ordinamento delle bolle

In questo tutorial imparerai come funziona il Bubble Sort. Inoltre, troverai esempi funzionanti di bubble sort in C, C ++, Java e Python.

Bubble sort è un algoritmo che confronta gli elementi adiacenti e scambia le loro posizioni se non sono nell'ordine previsto. L'ordine può essere crescente o decrescente.

Come funziona Bubble Sort?

Partendo dal primo indice, confronta il primo e il secondo elemento, se il primo elemento è maggiore del secondo vengono scambiati.
Ora confronta il secondo e il terzo elemento. Scambiali se non sono in ordine.
Il processo di cui sopra va avanti fino all'ultimo elemento. Confronta gli elementi adiacenti
Lo stesso processo va avanti per le restanti iterazioni. Dopo ogni iterazione, l'elemento più grande tra gli elementi non ordinati viene posizionato alla fine.
In ogni iterazione, il confronto avviene fino all'ultimo elemento non ordinato.
La matrice viene ordinata quando tutti gli elementi non ordinati vengono posizionati nelle posizioni corrette. Confronta gli elementi adiacenti Confronta gli elementi adiacenti Confronta gli elementi adiacenti

Algoritmo di ordinamento delle bolle

 bubbleSort (array) per i rightElement scambia leftElement e rightElement end bubbleSort

Esempi di Python, Java e C / C ++

Python Java C C ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Bubble Sort ottimizzato

Nel codice precedente, vengono effettuati tutti i confronti possibili anche se l'array è già ordinato. Aumenta il tempo di esecuzione.

Il codice può essere ottimizzato introducendo una variabile aggiuntiva scambiata. Dopo ogni iterazione, se non è in corso lo scambio, non è necessario eseguire ulteriori cicli.

In tal caso, la variabile scambiata è impostata su false. Pertanto, possiamo impedire ulteriori iterazioni.

L'algoritmo per l'ordinamento delle bolle ottimizzato è

 bubbleSort (array) scambiato <- false per i rightElement swap leftElement e rightElement scambiati <- true end bubbleSort

Esempi di Bubble Sort ottimizzati

Python Java C C +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Complessità

Bubble Sort è uno degli algoritmi di ordinamento più semplici. Due cicli sono implementati nell'algoritmo.

Ciclo	Numero di confronti
1 °	(n-1)
2 °	(n-2)
3 °	(n-3)
….	…
ultimo	1

Numero di confronti: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 quasi uguale an ²

Complessità: O (n ² )

Inoltre, possiamo analizzare la complessità semplicemente osservando il numero di loop. Ci sono 2 loop quindi la complessità èn*n = n²

Complessità temporali:

Complessità del caso peggiore: se vogliamo ordinare in ordine crescente e l'array è in ordine decrescente, si verifica il caso peggiore.O(n²)
Complessità caso migliore:O(n)
se l'array è già ordinato, non è necessario eseguire l'ordinamento.
Complessità case media: si verifica quando gli elementi dell'array sono in ordine confuso (né ascendente né discendente).O(n²)

Complessità spaziale: la
complessità dello spazio è O(1)dovuta al fatto che per lo scambio viene utilizzata una temperatura variabile aggiuntiva.

Nell'algoritmo ottimizzato, la variabile scambiata aumenta così la complessità dello spazio, rendendola O(2).