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 5Entrada: 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:
- El bucle exterior atraviesa la array dada (N – 1) veces.
- El ciclo interno atraviesa la array e intercambia dos elementos adyacentes si arr[i] > arr[i + 1] , por cada i sobre el rango [0, N – 1] .
- 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)