# 3.1.4. Selection Sort

# Implementation

T(n) = O(n^2)

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

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

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

# Example

# Run-Time Analysis

Worst case
- No. of comparisons
  
  \sum_{i=0}^{n-2} (n-i-1) = \frac {n(n-1)} 2 = O (\frac {n^2} {2})
- No. of record assignments
  
  3(n-1) = O(3n)
Average case
- No. of comparisons
  
  \sum_{i=0}^{n-2} (n-i-1) = \frac {n(n-1)} 2 = O (\frac {n^2} {2})
- No. of record assignments
  
  3(n-1) = O(3n)
[생각해보기] If we code like “if (i != cur) SWAP(A[i], A[cur]);”, what is the average cost?

alg