# Java program for Bubble Sort using recursive Approach

By | June 1, 2020

In the previous post,  Java program for Bubble Sort using Iterative Approach We learned how to write a java program for bubble sort using the Recursive method.
In this post, we will talk and learn about How to Write a Java program for Bubble Sort using Recursive Approach

Out of the three simple sorting algorithms, bubble sort, insertion sort, and selection sort. The bubble sort is considered the simplest sorting algorithm and it is the slowest too because of a large number of swaps and comparisons.

How Bubble sort works

In the bubble sort algorithm, we start by comparing the first two elements (index 0 and index 1). If the element at index 0 is greater than the element at index 1 then these two elements are swapped. If it is not then we do nothing. Then the next 2 elements have to compare (index 1 and index 2) and elements are swapped based on the same logic.

So, we have to follow the below steps in bubble sort:

We compare the adjacent elements. If the element at the left is greater than the element at the right then swap the elements then move one position right.

You continue to follow this until we reach the last element, by then we have the greatest element at the right. Since the biggest elements bubble up to the right end thus the named as “Bubble sort”

This is the first pass or iteration, in the next pass or iteration again we start from the two leftmost elements and compare the elements and swap if required. Because in first pass or iteration the rightmost element is already in its sorted position so this iteration runs till (N-1) elements. Where N is the total number of elements

For example, suppose we have an array  [50, 20, 60, 10]  then in the first iteration-

Initially, 50 is compared with 20, since 50 (element at left) is greater than 20 (element at right), elements are swapped making the array [20, 50, 60, 10].

Move over one position and compare 50 and 60, since 50 is not greater than 60 so nothing is done and array remains [20, 50, 60, 10].

Again, move over one position and compare 60 and 10, since 60 is greater than 10 elements are swapped giving us the array as [20, 50, 10, 60].

In the next iteration, the last element is not included in the comparison as it is already at its final or sorted position.

Sample input/output of the above program

Enter input Array Size:
1
Enter 1 Array Elements:
12
Original Array::

Sorted Array::


Enter input Array Size:
6
Enter 6 Array Elements:
123
23
45
67
10
29
Original Array::
[123, 23, 45, 67, 10, 29]
Sorted Array::
[10, 23, 29, 45, 67, 123]

#### Time and Space complexity of recursive bubble sort:

• We call here the same function recursively for each element of the array and inside the function, we loop till the given length of the array, So Time complexity is O(n ^ n) = O(n ^ 2).
• We recursively call the function for each element of the array, So Space complexity is O(n).

You May Also Like:

That’s all about Java program for Bubble Sort using Recursive Approach
If you have any feedback or suggestion please feel free to drop in below comment box.