- Forward


Bubble Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC 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 SMYC Forward

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

An Example
Back SMYC 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 SMYC 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 SMYC 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 SMYC Forward
cppexamples/sorting/BubbleSort.cpp
 
Efficiency Analysis
Back SMYC 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 SMYC 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 -