Antecedentes: Bubble Sort es el algoritmo de clasificación más simple que funciona intercambiando repetidamente los elementos adyacentes si están en el orden incorrecto. El siguiente es el algoritmo iterativo de clasificación de burbujas:
// Iterative Bubble Sort
bubbleSort(arr[], n)
{
for (i = 0; i n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
swap(arr[j], arr[j+1]);
}
Idea de recursividad.
- Caso base: si el tamaño de la array es 1, regrese.
- Realice una pasada de Bubble Sort normal. Este pase corrige el último elemento del subarreglo actual.
- Se repite para todos los elementos excepto el último del subarreglo actual.
// C/C++ program for recursive implementation
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
// Base case
if (n == 1)
return;
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (int i=0; i<n-1; i++)
if (arr[i] > arr[i+1])
swap(arr[i], arr[i+1]);
// Largest element is fixed,
// recur for remaining array
bubbleSort(arr, n-1);
}
/* Function to print an array */
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array : \n");
printArray(arr, n);
return 0;
}
Complejidad temporal : O(n*n)
Espacio auxiliar : O(1)
¡ Consulte el artículo completo sobre Clasificación de burbujas recursiva para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA