- Forward


Bubble Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • A Popular Motivation:
    • Between 25% and 50% of computing time in commercial applications is devoted to sorting
    • Hence, it is important to consider the efficiency of sorting algorithms
  • My Motivation:
    • The issues that arise are illustrative of the issues that arise when developing other algorithms
    • They provide good examples of how to find the efficiency of an algorithm
The Bubble Sort Algorithm
Back Forward

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

An Example
Back Forward
  • The Array to Sort:
    • The six-element array (8, 4, 7, 3, 9, 3)
  • The first inner iteration:
    • The 3 in element 5 is swapped with the 9 in element 4 as follows:
    • 8 4 7 3 3 9
  • The second inner iteration:
    • The 3 in element 3 is compared to the 3 in element 4 and is left in place:
    • 8 4 7 3 3 9
  • The rest of the inner iterations:
    • 8 4 3 7 3 9
      8 3 4 7 3 9
      3 8 4 7 3 9
An Example (cont.)
Back Forward
  • The second outer loop:
    • The inner loop is repeated, except now it stops before considering element 0
  • The iterations:
    • 3 8 4 7 3 9
      3 8 4 3 7 9
      3 8 3 4 7 9
      3 3 8 4 7 9
An Example (cont.)
Back Forward

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
Back Forward
cppexamples/sorting/BubbleSort.cpp
 
Efficiency Analysis
Back Forward
  • Number of Outer Iterations:
    • \(n-1\)
  • Number of Inner Iterations:
    • \(n-1\) for iteration 1
    • \(n-2\) for iteration 2
    • etc...
Efficiency Analysis
Back Forward
  • Worst Case Running "Time":
    • \( T(n) = [n-1] + [n-2] + \cdots + [n-(n-2)] + [n-(n-1)] = n \cdot (n-1) - \sum_{i=1}^{n-1} i \)
  • The Arithmetic Series:
    • \( 1 + 2 + 3 + \cdots + (m-1) + m = [m \cdot (m+1)] / 2 \)
  • Setting \(m = (n-1)\):
    • \( 1 + 2 + 3 + \cdots + (n-1) = [(n-1) \cdot n] / 2 \)
    • \( T(n) = n \cdot (n-1) - [n \cdot (n-1)] / 2 = [n \cdot (n - 1)]/2 = 0.5 \cdot (n^2 - n) = 0.5 \cdot n^2 - 0.5 \cdot n \)
  • So:
    • \( T(n) = O(n^2) \)
There's Always More to Learn
Back -