# 3.1.5. Bubble Sort

In

# Example

# Implementation

#define SWAP(a, b){
    item_type tmp;
    tmp = a;
    a = b;
    b = tmp;
}

void bubble_sort(item_type *A, int n){
    int i, j;

    for (i = 0; i < n - 1; i++){
        for (j = n - 1; j > i; j--){
            if (A[j] < A[j - 1])
                SWAP(A[j], A[j - 1]);
        }
    }
}

# Run-Time Analysis

Refer to The Art of Computer Programming (Vol. 3)
Worst Case
- No. of comparisons
  
  \sum_{i=1}^{n-1} (n-1-i) = \frac {n(n-1)} 2 = O (\frac {n^2} {2})
- No. of record assignments
  
  $\sum_^{3i = \frac 3 2 n(n-1)= O (\frac {3} {2} n}2) $
Average case
- No. of comparisons
  
  \sum_{i=1}^{n-1} (n-1-i) = \frac {n(n-1)} 2 = O (\frac {n^2} {2})
- No. of record assignments
  
  $\frac 1 2 \sum_^{3i = \frac 3 2 n(n-1)= O (\frac {3} {4} n}2) $

alg