Bubble sort
Ultimo aggiornamento
Il bubble sort scorre ripetutamente la lista, confronta ogni coppia di elementi adiacenti e li scambia se sono nell'ordine sbagliato. Dopo ogni passata completa, il valore più grande rimasto è "salito come una bolla" fino alla sua posizione corretta in fondo, quindi ogni passata esamina un elemento in meno. Premi play qui sopra per vedere confronti e scambi, o seguili uno alla volta.
È uno degli algoritmi di ordinamento più facili da capire, e questo lo rende un ottimo primo algoritmo, ma il suo tempo di esecuzione O(n²) lo rende poco pratico per input grandi.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(n) | Già ordinato, con un controllo di uscita anticipata |
| Caso medio | O(n²) | Ordine casuale |
| Caso peggiore | O(n²) | Ordinato al contrario |
| Spazio | O(1) | In loco, solo una variabile temporanea |
| Stabile | Sì | Gli elementi uguali mantengono il loro ordine relativo |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Parti dall'inizio dell'array. |
| 2 | Confronta l'elemento corrente con il successivo. |
| 3 | Se sono fuori ordine, scambiali. |
| 4 | Spostati di una posizione a destra e ripeti fino alla fine (una passata). |
| 5 | Ripeti le passate; ogni passata fissa un altro elemento in fondo. |
| 6 | Fermati quando una passata completa non fa scambi. |
Esempio svolto
Ordinamento di [5, 2, 4, 1]:
| Passata | Array | Azione |
|---|---|---|
| 1 | [2, 4, 1, 5] | Scambia 5,2, poi 5,4, poi 5,1; 5 sale fino in fondo. |
| 2 | [2, 1, 4, 5] | 2,4 in ordine; scambia 4,1; 4,5 in ordine; ora 4 è al suo posto. |
| 3 | [1, 2, 4, 5] | Scambia 2,1; il resto è già in ordine; 2 è al suo posto. |
| 4 | [1, 2, 4, 5] | Una passata completa non fa scambi, quindi l'array è ordinato e l'algoritmo si ferma. |
Quando usare il bubble sort
| Usalo quando | Evitalo quando |
|---|---|
| Insegni o impari come funzionano gli ordinamenti per confronto | Ordini input grandi, dove O(n²) è decisamente troppo lento |
L'input è minuscolo o quasi ordinato (con l'uscita anticipata si avvicina a O(n)) | Ti serve l'ordinamento generico più veloce: usa quicksort o merge sort |
| Ti serve un ordinamento stabile e in loco con pochissimo codice | I dati sono in ordine casuale e le prestazioni contano |
| Vuoi scoprire con una sola passata se una lista corta è già ordinata | Molte scritture sono costose (ad es. memoria flash); il selection sort fa meno scambi |
Codice Bubble Sort
Un'implementazione di Bubble Sort pulita ed eseguibile in Python, JavaScript, Java, C++, C, Pseudocode. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Bubble Sort in Python
Python
1def bubble_sort(a):2 n = len(a)3 for i in range(n - 1):4 swapped = False5 for j in range(n - 1 - i):6 if a[j] > a[j + 1]:7 a[j], a[j + 1] = a[j + 1], a[j]8 swapped = True9 if not swapped:10 break # no swaps means the list is already sorted11 return a12
13
14nums = [5, 1, 4, 2, 8]15print("Before:", nums)16bubble_sort(nums)17print("After: ", nums)Codice Bubble Sort in JavaScript
JavaScript
1function bubbleSort(a) {2 for (let end = a.length - 1; end > 0; end--) {3 let swapped = false;4 for (let j = 0; j < end; j++) {5 if (a[j] > a[j + 1]) {6 [a[j], a[j + 1]] = [a[j + 1], a[j]];7 swapped = true;8 }9 }10 if (!swapped) break; // Already sorted: stop early11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", bubbleSort([...data]));Codice Bubble Sort in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void bubbleSort(int[] arr) {5 for (int i = arr.length - 1; i > 0; i--) {6 boolean swapped = false;7 for (int j = 0; j < i; j++) {8 if (arr[j] > arr[j + 1]) {9 int tmp = arr[j];10 arr[j] = arr[j + 1];11 arr[j + 1] = tmp;12 swapped = true;13 }14 }15 if (!swapped) break; // already sorted16 }17 }18
19 public static void main(String[] args) {20 int[] arr = {5, 1, 4, 2, 8, 3};21 System.out.println("Before: " + Arrays.toString(arr));22 bubbleSort(arr);23 System.out.println("After: " + Arrays.toString(arr));24 }25}Codice Bubble Sort in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void bubbleSort(std::vector<int>& a) {11 for (size_t pass = 0; pass + 1 < a.size(); ++pass) {12 bool swapped = false;13 // Each pass bubbles the largest remaining value to the end14 for (size_t j = 0; j + 1 < a.size() - pass; ++j) {15 if (a[j] > a[j + 1]) {16 std::swap(a[j], a[j + 1]);17 swapped = true;18 }19 }20 if (!swapped) break; // already sorted21 }22}23
24int main() {25 std::vector<int> data = {5, 1, 4, 2, 8, 3};26 std::cout << "Before: ";27 printVec(data);28 bubbleSort(data);29 std::cout << "After: ";30 printVec(data);31 return 0;32}Codice Bubble Sort in C
C
1#include <stdbool.h>2#include <stdio.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void bubbleSort(int a[], int n) {10 for (int pass = 0; pass < n - 1; pass++) {11 bool swapped = false;12 // Each pass bubbles the largest remaining value to the end13 for (int j = 0; j < n - 1 - pass; j++) {14 if (a[j] > a[j + 1]) {15 int tmp = a[j];16 a[j] = a[j + 1];17 a[j + 1] = tmp;18 swapped = true;19 }20 }21 if (!swapped) break; // already sorted22 }23}24
25int main(void) {26 int data[] = {5, 1, 4, 2, 8, 3};27 int n = sizeof(data) / sizeof(data[0]);28 printf("Before: ");29 printArr(data, n);30 bubbleSort(data, n);31 printf("After: ");32 printArr(data, n);33 return 0;34}Codice Bubble Sort in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12DECLARE j : INTEGER13DECLARE temp : INTEGER14
15// Bubble the largest remaining value to the end on each pass16FOR i ← 1 TO n - 117 FOR j ← 1 TO n - i18 IF nums[j] > nums[j + 1] THEN19 temp ← nums[j]20 nums[j] ← nums[j + 1]21 nums[j + 1] ← temp22 ENDIF23 NEXT j24NEXT i25
26FOR i ← 1 TO n27 OUTPUT nums[i]28NEXT iDomande frequenti sul bubble sort
Qual è la complessità temporale del bubble sort?
Il bubble sort richiede tempo
O(n²) nel caso medio e peggiore a causa dei cicli annidati. Con l'ottimizzazione dell'uscita anticipata può arrivare a O(n) su un array già ordinato. Usa O(1) di spazio extra.Il bubble sort è stabile?
Sì. Il bubble sort scambia elementi adiacenti solo quando sono strettamente fuori ordine, quindi gli elementi uguali non si scavalcano mai e mantengono il loro ordine relativo originale.
Perché si chiama bubble sort?
A ogni passata il valore più grande non ancora ordinato si sposta passo dopo passo verso la fine dell'array, come una bolla che sale in superficie: da qui il nome "bubble" (bolla).
Qual è la differenza tra bubble sort e insertion sort?
Entrambi richiedono
O(n²) e sono stabili e in loco, ma spostano i dati in modo diverso: il bubble sort scambia ripetutamente coppie adiacenti fuori ordine, mentre l'insertion sort prende ogni elemento e lo fa scorrere all'indietro fino al suo posto nel prefisso ordinato. L'insertion sort di solito fa meno scritture ed è più veloce in pratica, soprattutto su dati quasi ordinati.Quando conviene usare il bubble sort invece del quicksort?
Quasi mai per carichi di lavoro reali: il tempo medio
O(n log n) del quicksort schiaccia l'O(n²) del bubble sort su qualsiasi input che non sia minuscolo. Il bubble sort vale la pena solo quando la lista è molto piccola o quasi ordinata, o quando vuoi l'ordinamento stabile più semplice possibile per insegnare.L'ottimizzazione dell'uscita anticipata cambia il caso peggiore del bubble sort?
No. Tenere traccia degli scambi fatti in una passata permette al bubble sort di fermarsi prima e arrivare a
O(n) su input già ordinati, ma un array ordinato al contrario richiede comunque tutti i confronti, quindi il caso peggiore resta O(n²). L'ottimizzazione aiuta solo nel caso migliore e in quelli quasi ordinati.Risorse correlate
Altre visualizzazioni
