Ordenamiento de burbuja recursiva

1. Algoritmo recursivo de ordenamiento de burbuja
2. Ejemplo de algoritmo recursivo de Ordenamiento de burbuja
3. Implementación del algoritmo recursivo Ordenamiento de burbuja
4. Complejidad del algoritmo Ordenamiento de burbuja

La ordenamiento de burbuja es un algoritmo de ordenación simple. Funciona mediante la comparación repetida de elementos adyacentes y el intercambio de los mismos si están en el orden incorrecto. Las comparaciones repetidas hacen que el elemento más pequeño/más grande se desplace hacia el final de la array, por lo que este algoritmo se denomina ordenamiento de burbuja. Aunque es ineficiente, sigue siendo la base de los algoritmos de ordenación.

Algoritmo recursivo de ordenamiento de burbuja

Supongamos que tenemos una array sin ordenar A[] que contiene n elementos.

Ejemplo de algoritmo recursivo de Ordenamiento de burbuja

Supongamos que tenemos el array (5,3,4,2,1). Vamos a ordenarlo utilizando el algoritmo de ordenamiento de burbuja.

• Primer pase:

• Segundo pase:

• Tercer pase:

• Cuarto pase:

Obtenemos la array ordenada después de la cuarta pasada - (1 2 3 4 5)

Implementación del algoritmo recursivo Ordenamiento de burbuja

#include <bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n) {
  if (n == 1) return;

  for (int i = 0; i < n - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      swap(arr[i], arr[i + 1]);
    }
  }

  bubbleSort(arr, n - 1);
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubbleSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo Ordenamiento de burbuja

Complejidad de tiempo

• Caso medio

Por término medio, se realizan n-i comparaciones en la quinta pasada de la ordenamiento de burbuja. Por tanto, si hay n pases, la complejidad temporal media puede ser la siguiente.

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

Por tanto, la complejidad temporal es del orden de O(n²).

• El peor caso

El peor caso se da cuando el array está ordenado de forma inversa, y hay que realizar el máximo número de comparaciones e intercambios.

La complejidad temporal en el peor caso es del orden de O(n²).

• El mejor caso

El mejor caso se da cuando la array ya está ordenada, y entonces sólo se necesitan N comparaciones.

La complejidad temporal en el mejor caso es O(n).

Complejidad espacial

La complejidad espacial de este algoritmo es O(n) debido a las llamadas recursivas almacenadas dentro de la pila.