Bubble Sort

Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n²) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.

Algorithm

1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
2. If at least one swap has been done, repeat step 1.

You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.

Example. Sort {5, 1, 12, -5, 16} using bubble sort.

Complexity analysis

Average and worst case complexity of bubble sort is O(n²). Also, it makes O(n²) swaps in the worst case. Bubble sort is adaptive. It means that for almost sorted array it gives O(n) estimation. Avoid implementations, which don't check if the array is already sorted on every step (any swaps made). This check is necessary, in order to preserve adaptive property.

Turtles and rabbits

One more problem of bubble sort is that its running time badly depends on the initial order of the elements. Big elements (rabbits) go up fast, while small ones (turtles) go down very slow. This problem is solved in the Cocktail sort.

Turtle example. Thought, array {2, 3, 4, 5, 1} is almost sorted, it takes O(n²) iterations to sort an array. Element {1} is a turtle.

Rabbit example. Array {6, 1, 2, 3, 4, 5} is almost sorted too, but it takes O(n) iterations to sort it. Element {6} is a rabbit. This example demonstrates adaptive property of the bubble sort.

Code snippets

There are several ways to implement the bubble sort. Notice, that "swaps" check is absolutely necessary, in order to preserve adaptive property.

Java

public void bubbleSort(int[] arr) {

      boolean swapped = true;

      int j = 0;

      int tmp;

      while (swapped) {

            swapped = false;

            j++;

            for (int i = 0; i < arr.length - j; i++) {                                       

                  if (arr[i] > arr[i + 1]) {                          

                        tmp = arr[i];

                        arr[i] = arr[i + 1];

                        arr[i + 1] = tmp;

                        swapped = true;

                  }

            }                

      }

}

C++

void bubbleSort(int arr[], int n) {

      bool swapped = true;

      int j = 0;

      int tmp;

      while (swapped) {

            swapped = false;

            j++;

            for (int i = 0; i < n - j; i++) {

                  if (arr[i] > arr[i + 1]) {

                        tmp = arr[i];

                        arr[i] = arr[i + 1];

                        arr[i + 1] = tmp;

                        swapped = true;

                  }

            }

      }

}

Visualizers

1. Bubble Sort Animation (with source code line by line visualization)
2. Bubble Sort in Java Applets Centre
3. Animated Sorting Algorithms: Bubble Sort

Seven responses to "Bubble sort tutorial"

1. anlequynh on Apr 14, 2009 said:

   thank you!!!

2. SDSS on Mar 18, 2009 said:

   2 GUD, THNX FOR CLARIFYING!

3. guest on Mar 3, 2009 said:

   nice explanation
   thanks!!!!!

4. guest on Feb 25, 2009 said:

   thanx very much. it's very useful!

5. guest on Feb 22, 2009 said:

   Thanx Buddy!!!!
   Keep the good work up!!!!

6. anils.. on Feb 20, 2009 said:

   Nice way of explanation using diagrams. Thank U..

7. lakshman on Feb 13, 2009 said:

   it is very good

Leave a reply
Your name (optional):
Your e-mail (optional):
Message: