Wednesday, 27 Oct 2021

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