Ordenar una array usando Bubble Sort sin usar bucles

Dada una array arr[] que consta de N enteros, la tarea es ordenar la array dada mediante Bubble Sort sin usar bucles .

Ejemplos:

Entrada: arr[] = {1, 3, 4, 2, 5}
Salida: 1 2 3 4 5

Entrada: arr[] = {1, 3, 4, 2}
Salida: 1 2 3 4

Enfoque: La idea de implementar Bubble Sort sin usar bucles se basa en las siguientes observaciones:

  • El algoritmo de clasificación de Bubble Sort realiza los siguientes pasos:
  • Se puede observar que en cada N – 1 iteración, el elemento más grande sobre el rango [0, N – 1 – i] cambia a la posición (N – 1 – i) por cada i sobre el rango [0, N – 1 ] .
  • Por lo tanto, la idea es usar la recursividad para evitar bucles.

Siga los pasos a continuación para resolver el problema:

  • Considere los siguientes casos base: 
    • Si la array contiene un solo elemento, simplemente imprima la array.
    • Si la array contiene dos elementos, intercambie el par de elementos (si es necesario) para obtener una secuencia ordenada de elementos de la array. Imprime la array ordenada.
  • Almacene los primeros dos elementos de la array actual en variables, digamos a y b .
  • Inicialice una array, digamos bs[] , para almacenar los elementos restantes de la array.
  • Coloque el valor más pequeño entre a y b al frente de la array actual.
  • Repita recursivamente los pasos anteriores con una nueva array formada al agregar bs[] al final del valor más grande entre a y b .
  • Almacene la lista ordenada devuelta en una variable, digamos res[] .
  • Ahora, repita recursivamente los pasos anteriores con una nueva array formada agregando res[] (excluyendo el último elemento) al final de res[res.size() – 1] (el último elemento).
  • Después de completar los pasos anteriores, imprima la lista devuelta .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to implement bubble
// sort without using loops
vector<int> bubble_sort(vector<int> ar)
{
 
  // Base Case: If array
  // contains a single element
  if (ar.size() <= 1)
    return ar;
 
  // Base Case: If array
  // contains two elements
  if (ar.size() == 2){
    if(ar[0] < ar[1])
      return ar;
    else
      return {ar[1], ar[0]};
  }
 
  // Store the first two elements
  // of the list in variables a and b
  int a = ar[0];
  int b = ar[1];
 
  // Store remaining elements
  // in the list bs
  vector<int> bs;
  for(int i = 2; i < ar.size(); i++)
    bs.push_back(ar[i]);
 
  // Store the list after
  // each recursive call
  vector<int> res;
   
  // If a < b
  if (a < b){
    vector<int> temp1;
    temp1.push_back(b);
    for(int i = 0; i < bs.size(); i++)
      temp1.push_back(bs[i]);
    vector<int> v = bubble_sort(temp1);
    v.insert(v.begin(), a);
    res = v;
  }
 
  // Otherwise, if b >= a
  else{
    vector<int> temp1;
    temp1.push_back(a);
    for(int i = 0; i < bs.size(); i++)
      temp1.push_back(bs[i]);
    vector<int> v = bubble_sort(temp1);
    v.insert(v.begin(), b);
    res = v;
  }
 
  // Recursively call for the list
  // less than the last element and
  // and return the newly formed list
  vector<int> pass;
  for(int i = 0; i < res.size() - 1; i++)
    pass.push_back(res[i]);
 
  vector<int> ans = bubble_sort(pass);
  ans.push_back(res[res.size() - 1]);
  return ans;
 
}
 
// Driver Code
int main()
{
 
  vector<int> arr{1, 3, 4, 5, 6, 2};
  vector<int> res = bubble_sort(arr);
 
  // Print the array
  for(int i = 0; i < res.size(); i++)
    cout << res[i] << " ";
}
 
// This code is contributed by ipg2016107.

Java

// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to implement bubble
  // sort without using loops
  static ArrayList<Integer> bubble_sort(ArrayList<Integer> ar)
  {
 
    // Base Case: If array
    // contains a single element
    if (ar.size() <= 1)
      return ar;
 
    // Base Case: If array
    // contains two elements
    if (ar.size() == 2) {
      if (ar.get(0) < ar.get(1))
        return ar;
      else
        return new ArrayList<Integer>(
        Arrays.asList(ar.get(1), ar.get(0)));
    }
 
    // Store the first two elements
    // of the list in variables a and b
    int a = ar.get(0);
    int b = ar.get(1);
 
    // Store remaining elements
    // in the list bs
    ArrayList<Integer> bs = new ArrayList<>();
    for (int i = 2; i < ar.size(); i++)
      bs.add(ar.get(i));
 
    // Store the list after
    // each recursive call
    ArrayList<Integer> res = new ArrayList<>();
 
    // If a < b
    if (a < b) {
      ArrayList<Integer> temp1 = new ArrayList<>();
      temp1.add(b);
      for (int i = 0; i < bs.size(); i++)
        temp1.add(bs.get(i));
 
      ArrayList<Integer> v = bubble_sort(temp1);
      v.add(0, a);
      res = v;
    }
 
    // Otherwise, if b >= a
    else {
      ArrayList<Integer> temp1 = new ArrayList<>();
      temp1.add(a);
      for (int i = 0; i < bs.size(); i++)
        temp1.add(bs.get(i));
 
      ArrayList<Integer> v = bubble_sort(temp1);
      v.add(0, b);
      res = v;
    }
 
    // Recursively call for the list
    // less than the last element and
    // and return the newly formed list
    ArrayList<Integer> pass = new ArrayList<>();
    for (int i = 0; i < res.size() - 1; i++)
      pass.add(res.get(i));
 
    ArrayList<Integer> ans = bubble_sort(pass);
    ans.add(res.get(res.size() - 1));
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    ArrayList<Integer> arr = new ArrayList<Integer>(
      Arrays.asList(1, 3, 4, 5, 6, 2));
    ArrayList<Integer> res = bubble_sort(arr);
 
    // Print the array
    for (int i = 0; i < res.size(); i++)
      System.out.print(res.get(i) + " ");
  }
}
 
// This code is contributed by Kingash.

Python3

# Python3 program for the above approach
 
# Function to implement bubble
# sort without using loops
def bubble_sort(ar):
   
    # Base Case: If array
    # contains a single element
    if len(ar) <= 1:
        return ar
       
    # Base Case: If array
    # contains two elements
    if len(ar) == 2:
        return ar if ar[0] < ar[1] else [ar[1], ar[0]]
 
    # Store the first two elements
    # of the list in variables a and b
    a, b = ar[0], ar[1]
 
    # Store remaining elements
    # in the list bs
    bs = ar[2:]
 
    # Store the list after
    # each recursive call
    res = []
     
    # If a < b
    if a < b:
        res = [a] + bubble_sort([b] + bs)
         
    # Otherwise, if b >= a
    else:
        res = [b] + bubble_sort([a] + bs)
         
    # Recursively call for the list
    # less than the last element and
    # and return the newly formed list
    return bubble_sort(res[:-1]) + res[-1:]
 
 
# Driver Code
 
arr = [1, 3, 4, 5, 6, 2]
res = bubble_sort(arr)
 
# Print the array
print(*res)

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to implement bubble
// sort without using loops
static List<int> bubble_sort(List<int> ar)
{
     
    // Base Case: If array
    // contains a single element
    List<int> temp = new List<int>();
     
    if (ar.Count <= 1)
        return ar;
 
    // Base Case: If array
    // contains two elements
    if (ar.Count == 2)
    {
        if (ar[0] < ar[1])
            return ar;
        else
        {
            temp.Add(ar[1]);
            temp.Add(ar[0]);
            return temp;
        }
    }
 
    // Store the first two elements
    // of the list in variables a and b
    int a = ar[0];
    int b = ar[1];
 
    // Store remaining elements
    // in the list bs
    List<int> bs = new List<int>();
    for(int i = 2; i < ar.Count; i++)
        bs.Add(ar[i]);
 
    // Store the list after
    // each recursive call
    List<int> res = new List<int>();
 
    // If a < b
    if (a < b)
    {
        List<int> temp1 = new List<int>();
        temp1.Add(b);
         
        for(int i = 0; i < bs.Count; i++)
            temp1.Add(bs[i]);
             
        List<int> v = bubble_sort(temp1);
        v.Insert(0, a);
        res = v;
    }
 
    // Otherwise, if b >= a
    else
    {
        List<int> temp1 = new List<int>();
        temp1.Add(a);
         
        for(int i = 0; i < bs.Count; i++)
            temp1.Add(bs[i]);
             
        List<int> v = bubble_sort(temp1);
        v.Insert(0, b);
        res = v;
    }
 
    // Recursively call for the list
    // less than the last element and
    // and return the newly formed list
    List<int> pass = new List<int>();
    for(int i = 0; i < res.Count - 1; i++)
        pass.Add(res[i]);
 
    List<int> ans = bubble_sort(pass);
    ans.Add(res[res.Count - 1]);
    return ans;
}
 
// Driver Code
public static void Main()
{
    List<int> arr = new List<int>{ 1, 3, 4, 5, 6, 2 };
    List<int> res = bubble_sort(arr);
 
    // Print the array
    for(int i = 0; i < res.Count; i++)
        Console.Write(res[i] + " ");
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to implement bubble
  // sort without using loops
function bubble_sort(ar)
{
    // Base Case: If array
    // contains a single element
    if (ar.length <= 1)
      return ar;
  
    // Base Case: If array
    // contains two elements
    if (ar.length == 2) {
      if (ar[0] < ar[1])
        return ar;
      else
        return [ar[1], ar[0]];
    }
  
    // Store the first two elements
    // of the list in variables a and b
    let a = ar[0];
    let b = ar[1];
  
    // Store remaining elements
    // in the list bs
    let bs = [];
    for (let i = 2; i < ar.length; i++)
      bs.push(ar[i]);
  
    // Store the list after
    // each recursive call
    let res = [];
  
    // If a < b
    if (a < b) {
      let temp1 = [];
      temp1.push(b);
      for (let i = 0; i < bs.length; i++)
        temp1.push(bs[i]);
  
      let v = bubble_sort(temp1);
      v.unshift(a);
      res = v;
    }
  
    // Otherwise, if b >= a
    else {
      let temp1 = [];
      temp1.push(a);
      for (let i = 0; i < bs.length; i++)
        temp1.push(bs[i]);
  
      let v = bubble_sort(temp1);
      v.unshift(b);
      res = v;
    }
  
    // Recursively call for the list
    // less than the last element and
    // and return the newly formed list
    let pass = [];
    for (let i = 0; i < res.length - 1; i++)
      pass.push(res[i]);
  
    let ans = bubble_sort(pass);
    ans.push(res[res.length - 1]);
    return ans;
}
 
// Driver Code
let  arr =[1, 3, 4, 5, 6, 2];
let res = bubble_sort(arr);
document.write(res.join(" "));
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción:

1 2 3 4 5 6

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por devansh42 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *