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. A continuación se muestra 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 arr[j+1])
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.
Java
// Java program for recursive implementation
// of Bubble sort
import java.util.Arrays;
public class GFG
{
// A function to implement bubble sort
static 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]
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
// Largest element is fixed,
// recur for remaining array
bubbleSort(arr, n-1);
}
// Driver Method
public static void main(String[] args)
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr, arr.length);
System.out.println("Sorted array : ");
System.out.println(Arrays.toString(arr));
}
}
Complejidad de tiempo: O(n 2 ) donde n es el tamaño de la array.
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