Hello Friends,
In this post, we will talk and learn about How to Write a Java program for Bubble Sort using Iterative Approach
Finally, we will also write an improved version of the bubble sort as well.
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 |
package com.kkjavatutorials.client; import java.util.Arrays; import java.util.Scanner; /** * Java program for Bubble Sort using Iterative 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); System.out.println("Sorted Array::"); System.out.println(Arrays.toString(sortedArray)); } catch (Exception e) { e.printStackTrace(); }finally { if(scanner != null) scanner.close(); } } private static int[] bubbleSort(int[] inputArray) { for (int i = 0; i < inputArray.length-1; i++) { for (int j = 0; j < inputArray.length-1-i; j++) { if(inputArray[j]>inputArray[j+1]) { int temp = inputArray[j]; inputArray[j] = inputArray[j+1]; inputArray[j+1] = temp; } } } return inputArray; } } |
Sample input/output of the above program
Enter input Array Size:
5
Enter 5 Array Elements:
100
23
45
67
12
Original Array::
[100, 23, 45, 67, 12]
Sorted Array::
[12, 23, 45, 67, 100]
Improved version of bubble sort when the input array is already in sorted order
|
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 61 62 63 64 65 |
package com.kkjavatutorials.client; import java.util.Arrays; import java.util.Scanner; /** * Java program for Bubble Sort using Iterative 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); System.out.println("Sorated Array::"); System.out.println(Arrays.toString(sortedArray)); } catch (Exception e) { e.printStackTrace(); }finally { if(scanner != null) scanner.close(); } } private static int[] bubbleSort(int[] inputArray) { boolean sorted = false; for (int i = 0; i < inputArray.length-1; i++) { for (int j = 0; j < inputArray.length-1-i; j++) { if(inputArray[j]>inputArray[j+1]) { int temp = inputArray[j]; inputArray[j] = inputArray[j+1]; inputArray[j+1] = temp; sorted = true; } } if(!sorted) { break; } } return inputArray; } } |
Sample input/output of the above program
Enter input Array Size:
10
Enter 10 Array Elements:
190
23
56
89
156
28
27
23
100
234
Original Array::
[190, 23, 56, 89, 156, 28, 27, 23, 100, 234]
Sorated Array::
[23, 23, 27, 28, 56, 89, 100, 156, 190, 234]
Time and Space complexity of Bubble sort:
In bubble sort, We use two nested loops that go through the elements that make it a complexity of n*n i.e. O(n^2). And in bubble sort, the number of swaps is also very high which makes it slower.
The bubble sort is an “in place” sorting algorithm that’s why there is no auxiliary space requirement so space complexity of Bubble sort is O(1).
You May Also Like:
Which data type would you choose for storing currency values like Trading Price in Java?
How would you print a given currency value for Indian Locale (INR Currency)?
Which classes in java are immutable ?
How would you round a double value to certain decimal Precision and Scale ?
What is BlockingQueue? How can we implement Producer and Consumer problem using Blocking Queue?
How to get number of available processors in Java ?
That’s all about Java program for Bubble Sort using Iterative Approach
If you have any feedback or suggestion please feel free to drop in blow comment box.