# 3.1.3. Insertion Sort

Insertion Sort: Example 1
Insertion Sort: Example 2
- Insertion : O(n+d) in the worst case over sequences that have d inversions
- When does the insertion sort run fast?
- 이러한 insertion sort의 성질을 quick sort의 성능 향상에 활용하자.

# Implementation

void insertion_sort(int *A, int n) { 
  int i, j, tmp;
  for (i = 1; i < n; i++) {
    tmp = A[i];
    j = i;
    while ((j > 0) && (tmp < A[j - 1])) {
      A[j] = A[j - 1];
      j--; 
    }A[j] = tmp; 
  }
}

Sort a list of elements by iteratively inserting a next element in a progressively growing sorted array.

#include <stdlib.h>
#include <string.h>
#include "sort.h"
int issort(void *data, int size, int esize, int (*compare)(const void *key1, const void *key2))
{
    char *a = data;
    void *key;
    int i, j;// Allocate storage for the key element.
if ((key = (char *)malloc(esize)) == NULL)
    return -1;
// Repeatedly insert a key element among the sorted elements.
for (j = 1; j < size; j++)
{
    memcpy(key, &a[j * esize], esize);
    i = j - 1;
    // Allocate storage for the key element.
    if ((key = (char *)malloc(esize)) == NULL)
        return -1;
    // Repeatedly insert a key element among the sorted elements.
    for (j = 1; j < size; j++)
    {
        memcpy(key, &a[j * esize], esize);
        i = j - 1;
        /* Determine the position at which to insert the key element. */ while (i >= 0 && compare(&a[i * esize], key) > 0)
        {

            memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
            i--;
        }
        memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
        i--;
    }
    memcpy(&a[(i + 1) * esize], key, esize);
}
// Free the storage allocated for sorting.
free(key);
return 0;

}

# Run-Time Analysis

Worst case
- No. of comparisons:
  
  1+2+ ...+n-1 = O(\frac {n^2}{2})
- No. of record assignments:
  
  1+2+ ...+n-1 = O(\frac {n^2}{2})
Average case
- No. of comparisons
  
  \sum_{i=1}^{n-1} {\frac{1+2+...+i+i}{i+1} } =\sum_{i=1}^{n-1} {(\frac{i}{2}+1-\frac{1}{i+1})} \\\approx \frac{(n-1)(n+4)}{4} - \ln n = O(\frac{n^2} 4)
- No. of record assignments
  
  \sum_{i=1}^{n-1} {\frac{0+1+2+...+i}{i+1} +2} = \frac{n(n-1)}{4}+2(n-1) = O(\frac{n^2}4)

# Example

alg