Skip to main content
Lesson 23 - Quadratic Sorting Algorithms
Lesson MenuPreviousNext
  
Bubble Sort page 4 of 10

  1. Bubble Sort is the simplest algorithm for sorting a set of data, and also the slowest. The procedure goes like this:

    1. Find the largest item and place it at the end of the items that were searched.
    2. Remove the largest item most recently found from the set to be searched and go to step a.
    3. (Repeat parts a. and b. until the number of items to be searched is zero.)

    The Bubble Sort algorithm uses the simplest method for determining the largest item in a list: it compares two items at a time and then moves on to compare the larger of the two with the next item in the list. After each comparison, the larger item must be identified and "swapped" into position to be compared with the next item.

  2. The following program implements the Bubble Sort algorithm.

    public static void bubbleSort(int[] list)
    {
      for (int outer = 0; outer < list.length - 1; outer++)
      {
        for (int inner = 0; inner < list.length-outer-1; inner++)
        {
          if (list[inner] > list[inner + 1])
          {
            //swap list[inner] & list[inner+1]
            int temp = list[inner];
            list[inner] = list[inner + 1];
            list[inner + 1] = temp;
          }
        }
      }
    }
    
  3. Given an array of 6 values, the loop variables outer and inner will evaluate as follows:

    When outer =inner ranges from
    0 to < (6 - outer - 1)
    00 to 4
    10 to 3
    20 to 2
    30 to 1
    40 to 0

  4. When outer = 0, then the inner loop will do 5 comparisons of values next to each other. As inner ranges from 0–4, it does the following comparisons:

    innerif list[inner] > list[inner + 1]
       
    0if list[0] > list[1]
    1if list[1] > list[2]
    ......
    4if list[4] > list[5]

  5. If (list[inner] > list[inner+1]) is true, then the values are out of order and a swap takes place. The swap takes three lines of code and uses a temporary variable temp.

  6. After the first pass (outer = 0), the largest value will be in its final resting place. When outer = 1, the inner loop only goes from 0 to 3 because a comparison between positions 4 and 5 is unnecessary. The inner loop is shrinking.

  7. Because of the presence of duplicate values this algorithm will result in a list sorted in nondecreasing order.

  8. Here is a small list of data to test your understanding of Bubble Sort. Write in the correct sequence of integers after each advance of outer.

    outer57958814256
    0
    1
    2
    3
    4


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.