Sort an array using Bubble Sort without using loops

Last Updated : 22 Jun, 2021

Given an array arr[] consisting of N integers, the task is to sort the given array by using Bubble Sort without using loops.

Examples:

Input: arr[] = {1, 3, 4, 2, 5}
Output: 1 2 3 4 5

Input: arr[] = {1, 3, 4, 2}
Output: 1 2 3 4

Approach: The idea to implement Bubble Sort without using loops is based on the following observations:

The sorting algorithm of Bubble Sort performs the following steps:
- The outer loop traverses the given array (N - 1) times.
- The inner loop traverses the array and swaps two adjacent elements if arr[i] > arr[i + 1], for every i over the range [0, N - 1].
It can be observed that in every N - 1 iteration, the largest element over the range [0, N - 1 - i] shifts to the position (N - 1 - i) for every i over the range [0, N - 1].
Therefore, the idea is to use recursion to avoid loops.

Follow the steps below to solve the problem:

Consider the following base cases:
- If the array contains a single element, simply print the array.
- If the array contains two elements, swap the pair of elements (if required) to obtain a sorted sequence of array elements. Print the sorted array.
Store the first two elements from the current array in variables, say a and b.
Initialize an array, say bs[], to store the remaining array elements.
Place the smaller value among a and b at the front of the current array.
Recursively repeat the above steps with a new array formed by appending bs[] to the end of the larger value among a and b.
Store the sorted list returned in a variable, say res[].
Now, recursively repeat the above steps with a new array formed by appending res[] (excluding the last element) to the end of res[res.size() - 1] ( the last element ).
After completing the above steps, print the returned list.

Below is the implementation of the above approach:

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# 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>

Output:

1 2 3 4 5 6

Time Complexity: O(N²)
Auxiliary Space: O(N)

Bubble Sort On Doubly Linked List

devansh42

Improve

Article Tags :

Practice Tags :

Sort an array using Bubble Sort without using loops

Similar Reads

Bubble Sort in different languages

Visualization of Bubble Sort

Thank You!

What kind of Experience do you want to share?