Bubble Sort in Java: Algorithm and Implementation

Bubble

BUBBLE SORT

• Bubble sort is used to sort unordered things.
• it repeatedly does only one task of swapping, if things are unordered.

Array

index      1            2           3          4            5

Array length is 5.

Algorithm

for i is 1 to length_of_array
|      for j is 1 to length_of_array -  i
|      |       if  array[j] > array[j+1]  then      
|      |       |           swape array[j] <~> array[j+1]

Java Code

import java.util.Scanner;
public class BubbleSort {
public static void bubbleSort(int[] array) {
int temp = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1 ; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter Length of Array : ");
int n = sc.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++)
array[i] = sc.nextInt();
BubbleSort.bubbleSort(array);
for (int i : array)
System.out.println(i);
}
}

Analysis

• Worst-case and average-case complexity: O(n^2) because in bubble sort algo. we are using a loop inside a loop.
• Best case complexity:  O(n) because in the best case all elements are already sorted so one-time loop will be executed and if condition will be checked.

• This algorithm does not need any extra memory so it is inplace algorithm.
• By tracing the algorithm we can found that if two elements have same value and index of the first element is smaller than the second element then after sorting, index of the first element will be smaller than the second element so bubble sort is a stable algorithm 

Better version or optimal algorithm

Algorithm

for i is 1 to length_of_array
|      swap = false
|      for j is 1 to length_of_array -  i
|      |       if  array[j] > array[j+1]  then      
|      |       |           swape array[j] <~> array[j+1]
|      |       |           set swap = true
|      if swap == false then 
|      |   exit

Java Code

import java.util.Scanner;
public class BubbleSort {
public static void bubbleSort(int[] array) {
int temp = 0;
boolean swap = false;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
swap = true;
}
}
if (swap == false)
break;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter Length of Array : ");
int n = sc.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++)
array[i] = sc.nextInt();
BubbleSort.bubbleSort(array);
for (int i : array)
System.out.println(i);
}
}

Facebook Google Twitter More

• Pinterest
• Linkedin
• Tumblr

Posted by : Denes Vaghani November 14, 2019 Tags : Data Structure

Subscribe by Email

Follow Updates Articles from This Blog via Email