Bubble Sort

This chapter helps you to understand:

• Basic Idea
• Java Implementation
• Performance
• Improvements

Basic Idea

The basic idea of Bubble Sort is to:

1. Data elements are grouped into two sections: a sorted section and an un-sorted section.

2. Go through every element in the un-sorted section and re-arrange its position with its neighbor to put the element with higher order on the higher position. At the end, the element with the highest order will be on top of the un-sorted section, and moved to the bottom of the sorted section.

3. Repeat step 2 until no more elements left in the un-sorted section.

In the sorting algorithm, if you watch the move of the elements with higher orders, they are like bubbles in the water, floating slowly from the bottom to the top.

Java Implementation

Here is my Java implementation of Bubble Sort algorithm:

/**
 * HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.
 * All sorting methods should have a signiture of 
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) 1999 by Dr. Herong Yang
 */
public class HyArrays {
   public static void bubbleSort(Object[] a, int fromIndex, 
      int toIndex) {
      Object d;
      for (int i=toIndex-1; i>fromIndex; i--) {
         boolean isSorted = true;
         for (int j=fromIndex; j<i; j++) {
            if (((Comparable)a[j]).compareTo(a[j+1])>0) {
               isSorted = false;
               d = a[j+1];
               a[j+1] = a[j];
               a[j] = d;
            }
         }
         if (isSorted) break;
      }   
   }
}

The following diagram illustrates how this implementation works:

                               
                                     --17  42  53  67  ...         92
                                    |       |   |   |               |
        +---+---+---------------+---+---+---+---+---+---------------+
        |   |                   |     /          
       29  36  11   ...        24  39                  
        |                           |   |                           |
fromIndex                           j   i                   toIndex-1

• Elements to be sorted are stored from "fromIndex" to "toIndex-1" inclusive.
• At the beginning of each iteration of loop "i", elements from "i+1" to "toIndex-1" are sorted.
• At the beginning of each iteration of loop "i", elements from "fromIndex" to "j+1" are not sorted.
• At the end of each interation of loop "i", element at "i" will be the element with the highest order in the un-sorted section.
• The "break" statement is there just in case when the un-sorted section happen to be already sorted.

Performance

Now let's see how it performs. I tried this implementation with my SortTest.java under JDK 1.3.1. Here are the results:

Array size: 1000
Average sorting time: 53 milliseconds
Number of tests: 1000
Performance: 53.0 O(N) nonaseconds
Performance: 5.318196590063668 O(N*Log2(N)) nonaseconds
Performance: 0.053 O(N*N) nonaseconds

Array size: 2000
Average sorting time: 217 milliseconds
Number of tests: 1000
Performance: 108.5 O(N) nonaseconds
Performance: 9.89441312937002 O(N*Log2(N)) nonaseconds
Performance: 0.05425 O(N*N) nonaseconds

Array size: 3000
Average sorting time: 488 milliseconds
Number of tests: 1000
Performance: 162.66666666666666 O(N) nonaseconds
Performance: 14.082783536776278 O(N*Log2(N)) nonaseconds
Performance: 0.05422222222222222 O(N*N) nonaseconds

Obviously, this is the worst performed sorting implementation so far, with 0.054 O(N*N).

Improvements

I don't see any ways to improve this.

This site Web