• 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

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

• 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

• 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

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

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;
      }
    }
  }
}
        

• Number of Outer Iterations:
  • \(n-1\)
• Number of Inner Iterations:
  • \(n-1\) for iteration 1
  • \(n-2\) for iteration 2
  • etc...

• 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) \)