Clasificación de burbuja recursiva

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.
Ejemplo:  
Primera pasada: 
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Aquí, el algoritmo compara los primeros dos elementos y cambia desde 5 > 1. 
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Cambiar desde 5 > 4 
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Cambiar desde 5 > 2 
( 1 4 2 5 8 ) –> ( 1 4 2 5 8), Ahora, dado que estos elementos ya están en orden (8 > 5), el algoritmo no los intercambia.
Segundo pase: 
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Intercambio desde 4 > 2 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
Ahora, la array ya está ordenada, pero nuestro algoritmo no sabe si está completa. El algoritmo necesita un pase completo sin ningún intercambio para saber que está ordenado.
Tercer Paso: 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ) 
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
El siguiente es un 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++)
     {
         if(arr[j] > arr[j+1])
             swap(arr[j], arr[j+1]);
     }
} 

Consulte Clasificación de burbujas para obtener más detalles.
¿Cómo implementarlo recursivamente?  
La clasificación por burbuja recursiva no tiene ventajas de rendimiento/implementación, pero puede ser una buena pregunta para verificar la comprensión de la clasificación por burbuja y la recursividad.
Si observamos más de cerca el algoritmo Bubble Sort, podemos notar que en el primer paso, movemos el elemento más grande hasta el final (suponiendo que se ordene en orden creciente). En el segundo paso, movemos el segundo elemento más grande a la penúltima posición y así sucesivamente. 
Idea de recursividad.  

1. Caso base: si el tamaño de la array es 1, regrese.
2. Realice una pasada de Bubble Sort normal. Este pase corrige el último elemento del subarreglo actual.
3. Se repite para todos los elementos excepto el último del subarreglo actual.

A continuación se muestra la implementación de la idea anterior.

// 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;
  
    int count = 0;
    // 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]);
            count++;
        }
  
      // Check if any recursion happens or not
      // If any recursion is not happen then return
      if (count==0)
           return;
  
    // 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;
}
  
// Code improved by Susobhan AKhuli

// 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;
  
         int count = 0;
        // 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;
                  count = count+1;
            }
  
          // Check if any recursion happens or not
          // If any recursion is not happen then return
         if (count == 0)
            return;
  
        // 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));
    }
}
  
// Code improved by Susobhan AKhuli

# Python Program for implementation of
# Recursive Bubble sort
class bubbleSort:
    """
     bubbleSort:
          function:
              bubbleSortRecursive : recursive 
                  function to sort array
              __str__ : format print of array
              __init__ : constructor 
                  function in python
          variables:
              self.array = contains array
              self.length = length of array
    """
  
    def __init__(self, array):
        self.array = array
        self.length = len(array)
  
    def __str__(self):
        return " ".join([str(x) 
                        for x in self.array])
  
    def bubbleSortRecursive(self, n=None):
        if n is None:
            n = self.length
        count = 0
  
        # Base case
        if n == 1:
            return
        # One pass of bubble sort. After
        # this pass, the largest element
        # is moved (or bubbled) to end.
        for i in range(n - 1):
            if self.array[i] > self.array[i + 1]:
                self.array[i], self.array[i +
                1] = self.array[i + 1], self.array[i]
                count = count + 1
  
        # Check if any recursion happens or not
          # If any recursion is not happen then return
        if (count==0):
            return
  
        # Largest element is fixed,
        #  recur for remaining array
        self.bubbleSortRecursive(n - 1)
  
# Driver Code
def main():
    array = [64, 34, 25, 12, 22, 11, 90]
      
    # Creating object for class
    sort = bubbleSort(array)
      
    # Sorting array
    sort.bubbleSortRecursive()
    print("Sorted array :\n", sort)
  
  
if __name__ == "__main__":
    main()
  
# Code contributed by Mohit Gupta_OMG, 
# improved by itsvinayak
# Code improved by Susobhan AKhuli

// C# program for recursive 
// implementation of Bubble sort
using System;
  
class GFG
{
  
// A function to implement
// bubble sort
static void bubbleSort(int []arr,   
                       int n)
{
    // Base case
    if (n == 1)
        return;
   
    int count = 0;
    // 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;
            count++;
        }
  
      // Check if any recursion happens or not
      // If any recursion is not happen then return
      if (count==0)
           return;
  
    // Largest element is fixed,
    // recur for remaining array
    bubbleSort(arr, n - 1);
}
  
// Driver code
static void Main()
{
    int []arr = {64, 34, 25, 
                 12, 22, 11, 90};
  
    bubbleSort(arr, arr.Length);
      
    Console.WriteLine("Sorted array : ");
    for(int i = 0; i < arr.Length; i++)
    Console.Write(arr[i] + " ");
}
}
  
// This code is contributed 
// by Sam007
  
// Code improved by Susobhan AKhuli

<script>
// javascript program for recursive
// implementation of Bubble sort
  
// A function to implement
// bubble sort
  function bubbleSort(arr, n)
{
  
    // Base case
    if (n == 1)
        return;
  
    var count = 0;
    // One pass of bubble
    // sort. After this pass,
    // the largest element
    // is moved (or bubbled)
    // to end.
      
    for (var i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
        {
          
            // swap arr[i], arr[i+1]
            var temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
            count++;
        }
  
    // Check if any recursion happens or not
      // If any recursion is not happen then return
    if (count == 0)
        return;
  
    // Largest element is fixed,
    // recur for remaining array
    bubbleSort(arr, n - 1);
}
   
// Driver code
  
    var arr = [64, 34, 25, 12, 22, 11, 90 ]
    bubbleSort(arr, arr.length);
    document.write("Sorted array : " + "<br>");
    for(var i = 0; i < arr.length; i++) {
    document.write(arr[i] + " ");
    }
      
    // This code is contributed by bunnyram19.
    // Code improved by Susobhan AKhuli
    </script>

Sorted array : 
11 12 22 25 34 64 90 

• Complejidad temporal: O(n*n)
• Espacio Auxiliar: O(n)

Echa un vistazo al curso de autoaprendizaje de DSA

Este artículo es una contribución de Suprotik Dey . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.