• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to footer
  • Core Java
  • Design Patterns
  • JSP
  • Servlets
  • Building Tools
  • jQuery
  • Spring
  • Hibernate
  • Mongo DB
  • More
    • HTML
    • SCJP
    • AJAX
    • UML
    • Struts
    • J2EE
    • Testing
    • Angular JS

J2EE Reference

  • Home
  • About Us
    • Java Learning Centers
  • Contact Us

bubble sort algorithm in java

June 12, 2015 By j2eereference Leave a Comment

Bubble sort algorithm in java

Bubble sort works by comparing two items in the list at a time. Bubble sort will always compare two consecutive items in the list, and swap them if they are out of order. If we assume that we start at the beginning of the list, this means that at each pass through the algorithm, the largest remaining item in the list will be placed at its proper location in the list.

Algorithm for bubble sort:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
for i=N-1 to 2
{
     set swap flag to false
     for j=1 to i
     {
         if list[j-1] > list[j]
                swap list[j-1] and list[j]
         set swap flag to true
     }
     if swap flag is false,
          break.
     The list is sorted.
}

Notice that in each pass, the largest item “bubbles” down the list until it settles in its final position. This is where bubble sort gets its name.

Example:

b1

b2

b3

b4

b5

b6

b7

Notice that only the largest value is correctly placed. All other values are still out of order, So we need to repeat this process.

Bubbling all the elements:

b8

 

If we have N elements, And if each time we bubble an element, we place it in its correct location. Then we repeat the “bubble up” process N– 1 times. This guarantees we’ll correctly  place all N elements.

 

Java implementation for bubble sort:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void bubbleSort(int[] list)
{
// this variable will indicate if the list is sorted on this pass
boolean isSorted;
for (int i=0; i<list.length-1; i++)
{
isSorted = true;
for (int j=0; j<list.length-i-1; j++)
{
if (list[j+1] < list[j])
{
// two items are out of order, so swap them
swap(list,j,j+1);
isSorted = false;
}
}
if (isSorted)
{
// we didn’t find anything to swap, so we’re done.
break;
}
}
}

 

Performance of bubble sort algorithm:

  1. The best case for bubble sort occurs when the list is already sorted. In this case, bubble sort makes one pass through the list, performing no swaps and N-1 comparisons.
  2. The worst case for bubble sort occurs when the list is in reverse order. In this case, every item will have to be swapped with every other item on every pass through the algorithm. The number of swaps in the worst case is each comparison results in a swap, so there are O(N2 ) swaps in bubble sort!
  3. The average case looks like the worst case: O(N2 ) comparisons and O(N2 ) swaps.

Let’s see whether bubble sort is stable and in-place or not:

Stability:

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array

Selection sort algorithm is not stable because:

Selection sort algorithm picks the minimum and swaps it with the element at current position.
Suppose the array is:5 2 3  8 4 5 6
Let’s distinguish the two 5’s as 5(a) and 5(b) .
So our array is:
5(a)  3 4  5(b) 2 6 8

After iteration 1:

3 4 5(a) 2 5(b) 6 8

after last iteration our array becomes:
2 3 4 5(a) 5(b) 6 8
Since now our array is in sorted order and we clearly see that 5(a) comes before 5(b) in initial array and in the sorted array also.
So we can clearly see that bubble sort is stable.

In place:

An in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes

As explained above, bubble sort is structured so that on each pass through the list the next largest element of the data is moved to its proper place. Therefore, to get all n elements in their correct places, the outer loop must be executed n times. It takes small data structure for swapping purpose. so the bubble sort is one of the in place algorithm.

Related Posts

  • Java Buzzwords
  • Anonymous Inner Class in Java
  • Network Programming – java.net Package
  • Java Regular Expressions
  • Method Local Inner Class in Java
  • URL Processing in Java
  • Difference between Stack and Heap memory
  • What is ThreadMXBean in java?
  • What is serialVersionUID
  • What is exchanger in concurrency?

Filed Under: Core Java

Reader Interactions

Leave a Reply Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Primary Sidebar

FOLLOW US ONLINE

  • View J2eereference-166104970118637’s profile on Facebook
  • View j2eereference’s profile on Twitter
  • View j2eereference’s profile on LinkedIn

Subscribe by email

Recent posts

  • Java Buzzwords
  • Anonymous Inner Class in Java
  • Network Programming – java.net Package
  • Java Regular Expressions
  • Method Local Inner Class in Java
  • URL Processing in Java
  • Iterator Design Pattern Implementation using Java
  • Strategy Design Pattern Implementation using Java
  • Decorator Design Pattern
  • Adapter Design Pattern Implementation using Java
  • JSF Composite Components
  • JSF UI Components
  • What is JavaServer Faces (JSF)?
  • GOF Design Patterns
  • History and Need for Design Patterns

Footer

Core Java
Design Patterns
JSP
Servlets
HTML
Building Tools
AJAX
SCJP
jQuery
Testing
Spring
UML
Struts
Java Centers
Java Training
Home
About Us
Contact Us
Copyright © j2eereference.com. All right reserved.