Bubble Sort

1. Algoritmo di ordinamento delle bolle
2. Esempio di algoritmo di ordinamento a bolle
3. Implementazione dell’algoritmo Bubble Sort
4. Complessità dell’algoritmo di ordinamento delle bolle

Bubble sort è un semplice algoritmo di ordinamento. Funziona confrontando ripetutamente gli elementi adiacenti e scambiandoli se sono nell’ordine sbagliato. I confronti ripetuti fanno comparire l’elemento più piccolo / più grande verso la fine dell’array, e quindi questo algoritmo è chiamato bubble sort. Sebbene inefficiente, rappresenta ancora la base per gli algoritmi di ordinamento.

Algoritmo di ordinamento delle bolle

Supponiamo di avere un array non ordinato A[] contenente n elementi.

Il passaggio 1 dell’algoritmo sopra è anche chiamato passaggio. Per ordinare un array di dimensione n, sono necessari n-1 passaggi.

Esempio di algoritmo di ordinamento a bolle

Supponiamo di avere l’array: (5,3,4,2,1). Lo ordineremo utilizzando l’algoritmo di ordinamento delle bolle.

• Primo passaggio:

• Secondo passaggio:

• Terzo passaggio:

• Quarto passaggio:

Otteniamo l’array ordinato dopo il quarto passaggio - (1 2 3 4 5)

Implementazione dell’algoritmo Bubble Sort

#include <iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubble_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complessità dell’algoritmo di ordinamento delle bolle

Complessità temporale

• Case nella media

In media, i confronti n-i vengono effettuati nel passaggio ith del bubble sort. Quindi, se ci sono n passaggi, la complessità temporale media può essere data da

(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2

Quindi la complessità temporale è dell’ordine di O(n²).

• Peggiore caso

Il caso peggiore si verifica quando l’array viene ordinato in modo inverso e deve essere eseguito il numero massimo di confronti e scambi.

La complessità temporale del caso peggiore è O(n²).

• Caso migliore

Il caso migliore si verifica quando la matrice è già ordinata e quindi sono necessari solo N confronti.

La complessità temporale nel migliore dei casi è O(n).

Complessità spaziale

La complessità dello spazio per questo algoritmo è O(n) perché non è richiesta alcuna memoria aggiuntiva oltre a una variabile temporanea.