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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
package com.kkjavatutorials.client; import java.util.Arrays; import java.util.Scanner; /** * Java program for Bubble Sort using recursive Approach * @author KK JavaTutorials * */ public class BubbleSortTest { public static void main(String[] args) { Scanner scanner = null; try { System.out.println("Enter input Array Size:"); scanner = new Scanner(System.in); int inputArraySize = scanner.nextInt(); int inputArray[] = new int[inputArraySize]; System.out.println("Enter " +inputArraySize+" Array Elements:"); for (int i = 0; i < inputArray.length; i++) { inputArray[i] = scanner.nextInt(); } System.out.println("Original Array::"); System.out.println(Arrays.toString(inputArray)); int sortedArray[] = bubbleSort(inputArray,inputArraySize); System.out.println("Sorted Array::"); System.out.println(Arrays.toString(sortedArray)); } catch (Exception e) { e.printStackTrace(); }finally { if(scanner != null) scanner.close(); } } //bubble Sort using recursive approach private static int[] bubbleSort(int[] inputArray, int inputArraySize) { if(inputArraySize == 1) return inputArray; for (int i = 0; i < inputArray.length-1; i++) { if(inputArray[i]>inputArray[i+1]) { int temp = inputArray[i]; inputArray[i] = inputArray[i+1]; inputArray[i+1] = temp; } } return bubbleSort(inputArray,inputArraySize-1); } } |
Sample input/output of the above program
Enter input Array Size:
1
Enter 1 Array Elements:
12
Original Array::
[12]
Sorted Array::
[12]
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:
Can We store a double value in a long type variable without casting?
How many ways we can create an object in Java?
Why Java is not 100% Object-oriented language?
What are the differences between 32-bit and 64-bit versions of Java?
Can we call static method with null object?
Can we override static method in Java?
What will be the output of following java program?
What is the difference Between java.util.Date and java.sql.Date in Java ?
What is difference between using Serializable & Externalizable Interfaces in Java?
Which Java data type would you choose for storing sensitive information, like passwords, and Why?
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.