$show=/label

Java Program to Optimized Bubble Sort - Java Implementation Algorithm

SHARE:

Java Optimized Bubble Sort. Learn program to write Optimized Bubble Sort with algorithm. Simplification of Bubble Sort Program With Different Inputs For Best Case And Worst Case.

Optimized Bubble Sort in Java

In this post, we will learn how to optimize the bubble sort algorithm. This is a very basic interview question in many product-based companies for freshers and 0-2 experience.

Of course, Bubble Sort is one of the slowest algorithms but still, we can optimize it for better performance and this is only for smaller sets of input.

If you do not know the bubble sort algorithm and how it works then please go through the below article for a better understating of optimization.


Optimized Bubble Sort in Java



More on How to write a Program on Bubble Sort

Areas to Optimize:

Where can we optimize it? The following are areas to think about optimization.

1) Consider example array : 9 5 7 3 1
   We will have to iterate 5 times from index 0 to 4.
   Iteration 1: when we run the inner loop 1st time then-largest value will be moved to the right side of it that is at an array n-1 position. Loop from index 0 to n-1
   5 7 3 1 9
   Iteration 2: In 2nd iteration of the inner loop, 2nd largest value will be moved to the second position from the right side of the array that is at the n-2 position. Loop from 0 to n-1. Observe here actually, value at n-1 position value is already sorted and having largest value from the above step. Here if we can run the loop till n-2 is an option for optimizing it.
   5 3 1 7 9
   Iteration 3: For 3rd iteration of the inner loop which is again loop from index 0 to n-1. After loop completion, 3rd largest value is at the n-3 position of the array. But loop is from 0 to n-1. Here also loop is not required till n-1 because n-1, n-2 elements are already sorted. and so on.....for remaining iterations.
   3 1 5 7 9
 
2) If a given array is already sorted.
   Eg.  1 3 5 7 9
   Consider the above array, which is already sorted. But using normal bubble sorting algorithm, we will have to go through the loop from index 0 to 4 for 5 times because the array length is 5.
 
3) Given array is not sorted, but it may become sorted at any point of time in the inner loop.
   Eg. 9 1 3 5 7
   We will have to iterate 5 times from index 0 to 4.
   Iteration 1: 1 3 5 7 9 --> swap is done.
   Iteration 2: Seems array is sorted. But, how to identify it is sorted is to iterate the loop from index 0 to 4, mark the flag as true if any swap is done using a boolean variable.
   Here it has become in the second iteration.
 
If we do these three then Bubble sort is optimized.

If you see any area to improve in this sorting, Please post in a comment.

Optimized Algorithm:

 n = length(inputArrayValues)
 isSwapped = true;
 iterateCount = 0;
    repeat
  isSwapped = false
        for i = 1 to n-1-iterateCount inclusive do
            if inputArrayValues[i-1] > inputArrayValues[i] then
                swap(inputArrayValues[i-1], inputArrayValues[i])
                isSwapped = true
            end if
        end for
    until not isSwapped

Optimized Bubble Sort Program:

package com.adeepdrive.sorting;

public class OptimizedBubbleSort {

 public static void main(String[] Args) {

  int[] inputArrayValues = { 9, 5, 7, 3, 1 };
  System.out.print("input array before sorting : ");
  printInputArray(inputArrayValues);
  boolean isSwapped = true;
  int iterateCount = 0;
  while (isSwapped) {
   isSwapped = false;
   for (int i = 0; i < inputArrayValues.length - 1 - iterateCount; i++) {
    if (inputArrayValues[i] > inputArrayValues[i + 1]) {
     int temp = inputArrayValues[i];
     inputArrayValues[i] = inputArrayValues[i + 1];
     inputArrayValues[i + 1] = temp;
     isSwapped = true;
    }
   }
   iterateCount++;
   System.out.print("\nIterate " + iterateCount + " : ");
   printInputArray(inputArrayValues);
  }
  System.out.print("\ninput array after sorting : ");
  printInputArray(inputArrayValues);
 }

 public static void printInputArray(int[] values) {
  for (int value : values) {
   System.out.print(value + " ");
  }
 }
}

Output 1 for input 1:

input array before sorting : 9 5 7 3 1
Iterate 1 : 5 7 3 1 9
Iterate 2 : 5 3 1 7 9
Iterate 3 : 3 1 5 7 9
Iterate 4 : 1 3 5 7 9
Iterate 5 : 1 3 5 7 9
input array after sorting : 1 3 5 7 9

Pass input array : int[] inputArrayValues = { 9, 1, 3, 5, 7 };


Output 2 for input 2:


input array before sorting : 9 1 3 5 7
Iterate 0 : 1 3 5 7 9
Iterate 1 : 1 3 5 7 9
input array after sorting : 1 3 5 7 9

See the differences between output 1 and output 2. If the array becomes sorted then it will exit from the loop.

This is how we optimize.

Please leave your questions in the comments section.

COMMENTS

BLOGGER

About Us

Author: Venkatesh - I love to learn and share the technical stuff.
Name

accumulo,1,ActiveMQ,2,Adsense,1,API,31,ArrayList,16,Arrays,3,Bean Creation,3,Bean Scopes,1,BiConsumer,1,Blogger Tips,1,Books,1,C Programming,1,Collection,4,Collections,21,Collector,1,Command Line,1,Compile Errors,1,Configurations,7,Constants,1,Control Statements,8,Conversions,5,Core Java,74,Corona India,1,Create,2,CSS,1,Date,2,Date Time API,3,Dictionary,1,Difference,1,Download,1,Eclipse,2,Efficiently,1,Error,1,Errors,1,Exception,1,Exceptions,3,Fast,1,Files,9,Float,1,Font,1,For examples,1,For loop examples,1,For Loop in Java,1,Form,1,Freshers,1,Function,3,Functional Interface,2,Garbage Collector,1,Generics,4,Git,4,Grant,1,Grep,1,HashMap,1,HomeBrew,2,HTML,2,HttpClient,2,Immutable,1,Inner for loops,1,Installation,1,Interview Questions,5,Iterate,2,Jackson API,3,Java,28,Java 10,1,Java 11,5,Java 12,5,Java 13,2,Java 14,2,java 5 For loop,1,Java 8,50,Java 9,1,Java Design Patterns,1,Java Files,1,Java for loop,1,Java Program,2,Java Programs,65,java.lang,5,java.util. function,1,jQuery,1,Kotlin,10,Kotlin Programs,6,Lambda,1,lang,29,Leap Year,1,live updates,1,Mac OS,2,Math,1,Maven,1,Method References,1,Mockito,1,MongoDB,3,Nested for loop,1,Nested for loop examples,1,New Features,1,Operations,1,Optional,4,Oracle,5,Oracle 18C,1,Partition,1,Patterns,1,Programs,1,Property,1,Python,2,Quarkus,1,Read,1,Real Time,1,Recursion,2,Remove,2,Rest API,1,Schedules,1,Serialization,1,Servlet,1,Sorting Techniques,8,Spring,2,Spring Boot,23,Spring Email,1,Spring MVC,1,Stream,3,Streams,12,String,48,String Programs,8,String Revese,1,Swing,1,System,1,Tags,1,Threads,9,Tomcat,1,Tomcat 8,1,Troubleshoot,16,Unix,2,Updates,3,util,5,While Loop,1,
ltr
item
JavaProgramTo.com: Java Program to Optimized Bubble Sort - Java Implementation Algorithm
Java Program to Optimized Bubble Sort - Java Implementation Algorithm
Java Optimized Bubble Sort. Learn program to write Optimized Bubble Sort with algorithm. Simplification of Bubble Sort Program With Different Inputs For Best Case And Worst Case.
https://4.bp.blogspot.com/-Jis5M5yIu-8/XKtv8IzJvXI/AAAAAAAABQI/TUCXbiiFTYwUjl-ApsOoPpH3ePEYgBaIwCLcBGAs/s400/Optimized%2BBubble%2BSort%2Bin%2BJava.PNG
https://4.bp.blogspot.com/-Jis5M5yIu-8/XKtv8IzJvXI/AAAAAAAABQI/TUCXbiiFTYwUjl-ApsOoPpH3ePEYgBaIwCLcBGAs/s72-c/Optimized%2BBubble%2BSort%2Bin%2BJava.PNG
JavaProgramTo.com
https://www.javaprogramto.com/2017/11/optimized-bubble-sort-in-java.html
https://www.javaprogramto.com/
https://www.javaprogramto.com/
https://www.javaprogramto.com/2017/11/optimized-bubble-sort-in-java.html
true
3124782013468838591
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content