JMU
Bubble Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
The Bubble Sort Algorithm

Iteratively swap adjacent elements, starting at the bottom, "bubbling" the smallest to the top

An Example
An Example (cont.)
An Example (cont.)

The Third Outer Loop

3 3 8 4 7 9
3 3 8 4 7 9
3 3 4 8 7 9

The Fourth Outer Loop

3 3 4 8 7 9
3 3 4 7 8 9

The Fifth Outer Loop

3 3 4 7 8 9

An Implementation
cppexamples/sorting/BubbleSort.cpp
        /**
 * Sort an array of integers using a bubble sort.
 *
 * Side Effects: The array is sorted  "in place".
 *
 * @param a        The array of integers
 * @param length   The number of elements in the array
 */
void sort(int a[], int length) {
  int bottom, i, temp;

  for (bottom = length - 1; bottom >= 1; bottom--) {
    for (i = 0; i < bottom; i++) {
      if (a[i] > a[i + 1]) {
        temp = a[i];
        a[i] = a[i + 1];
        a[i + 1] = temp;
      }
    }
  }
}
        
Efficiency Analysis
Efficiency Analysis