Sort an array using Bubble Sort without using loops

Sort an array using Bubble Sort without using loops

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:
• 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:

• Declare a function say bubbleSort(arr) which takes a list as an argument that returns a sorted list after performing the below steps:
  • Base Case: If the length of the current list is 1 then return the sorted list. Otherwise, if the length of the list is 2 then sort the list using only one swap and return the list.
  • Otherwise, take the first two elements of the list arr[] and store them in variables, say a and b, and the rest of the elements in a list, say ab[].
  • Check if a < b. If found to be true, then recursively call the function bubbleSort(b + ab[]), as the element a cannot be the largest element of the current list arr[].
  • Otherwise, call the function bubbleSort(a + ab[]) as b cannot be the largest element in the current list arr[]
  • Store the list returned from the above function call into a list, say res[], and store the last element of the list in a variable, say last.
  • Now, recursively call for the list with size one less than the current list res[], leaving the largest element res[-1] at the last index of the array res[].
  • Store the list returned from the above function call into res[].
  • Finally, return the list res[] after appending the last element, say last in the list res[].
• Call the function with the argument as the current list arr[], bubble_sort(arr).
• After completing the above steps, print the returned list.

Below is the implementation of the above approach:

Python3

def bubble_sort(ar):               if len(ar) <= 1:         return ar                   if len(ar) == 2:         return ar if ar[0] < ar[1] else [ar[1], ar[0]]                               a, b, bs = ar[0], ar[1], ar[2:]                  res = []                 if a < b:         res = [a] + bubble_sort([b] + bs)                     else:         res = [b] + bubble_sort([a] + bs)                               return bubble_sort(res[:-1]) + res[-1:]          arr = [1, 3, 4, 2, 5] res = bubble_sort(arr)    print(*res)

Output:

1 2 3 4 5

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)