---
title: 資料結構與演算法—插入排序 Insertion Sort
tags:
- 資料結構
- 演算法
---
# 資料結構與演算法—插入排序 Insertion Sort

**筆記頁面：**[資料結構與演算法](https://hackmd.io/@yuto0226/r1ZYDXL3a)

## Pseudo Code
<pre class="part" id="pseudocode">
<span class="pseudocode-title">INSERTION-SORT(A,n)</span>
<span class="line-number">1</span><span class="keyword">for</span> i = 2 <span class="keyword">to</span> n
<span class="line-number">2</span> key= A [i]
<span class="line-number">3</span> <span class="comment">// Insert A[i] into the sorted subarray A[1:i-1]</span>
<span class="line-number">4</span> j = i - 1
<span class="line-number">5</span> <span class="keyword">while</span> j > 0 and A[j] > key
<span class="line-number">6</span> A[j + 1] = A[j]
<span class="line-number">7</span> j = j - 1
<span class="line-number">8</span> A[j + 1] = key
</pre>

## 時間複雜度分析

| line | cost | times |
| ---- | ----- | --------------------- |
| 1 | $c_1$ | $n$ |
| 2 | $c_2$ | $n-1$ |
| 3 | $c_3$ | $n-1$ |
| 4 | $c_4$ | $n-1$ |
| 5 | $c_5$ | $\sum^n_{i=2}t_i$ |
| 6 | $c_6$ | $\sum^n_{i=2}(t_i-1)$ |
| 7 | $c_7$ | $\sum^n_{i=2}(t_i-1)$ |
| 8 | $c_8$ | $n-1$ |

$$
\begin{multline*}
T(n)=c_1n+c_2(n-1)+c_3(n-1)+c_4(n-1)+ \\
c_5\sum^n_{i=2}t_i+c_6\sum^n_{i=2}(t_i-1)+c_7\sum^n_{i=2}(t_i-1)+c_8(n-1)
\end{multline*}
$$

### Best Case
the best case occurs when the array is ==already sorted==
line 5-7 will never be executed

$$
\begin{align*}
\Rightarrow T(n)&=(c_1+c_2+c_3+c_4+c_8)n-(c_2+c_3+c_4+c_8) \\
let\ a&=c_1+c_2+c_3+c_4+c_8 \\
let\ b&=c_2+c_3+c_4+c_8 \\
\Rightarrow T(n)&=an-b
\end{align*}
$$

最佳情況所消耗之時間為線性增長的 $O(n)$

### Worst Case

最糟情況是每一次的排序，都要把要插入的值移到第一個位置。也就是說 5-7 行都會跑滿，使得$t_i=i$。因此我們可以將 Summation 的式子化簡：

$$
\begin{align*}
\sum^n_{i=2}t_i=\sum^n_{i=2}i=(\sum^n_{i=1}i)-1=&\frac{n(n+1)}{2}-1 \\
\sum^n_{i=2}(t_i-1)=\sum^n_{i=2}(i-1)=\sum^{n-1}_{i=1}i=\frac{(n-1)(n-1+1)}{2}=&\frac{n(n-1)}{2}
\end{align*}
$$

在將化簡後的式子帶入原式：

$$
\begin{align*}
\Rightarrow T(n)=&c_1n+c_2(n-1)+c_3(n-1)+c_4(n-1)+ \\
&c_5(\frac{n(n+1)}{2}-1)+c_6(\frac{n(n-1)}{2})+c_7(\frac{n(n-1)}{2})+c_8(n-1) \\
=&(\frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2})n^2+(c_1+c_2+c_3+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8)n \\
&-(c_2+c_4+c_5+c_8) \\
let\ a=&\frac{c_5}{2}+\frac{c_6}{2}+\frac{c_7}{2} \\
let\ b=&c_1+c_2+c_3+c_4+\frac{c_5}{2}-\frac{c_6}{2}-\frac{c_7}{2}+c_8 \\
let\ c=&c_2+c_4+c_5+c_8 \\
\Rightarrow T(n)=&an^2+bn-c
\end{align*}
$$

最糟情況所消耗之時間為指數增長的 $O(n^2)$

## C Code

void Insert_Sort(int *arr, int len) {
    
    // i is point to value to insert
	for(int i = 1; i < len; i++) {
		int item = arr[i];
		
		// shift back when sorted value is large than item
		int j = i - 1;
		for(; j >= 0 && arr[j] > item; j--) {
			arr[j+1] = arr[j];
		}
        
		// insert into empty position
		arr[j+1] = item;
	}
}

<style>
.keyword{
font-weight: bold;
}
.comment{
color: rgb(185 28 28);
}
.pseudocode-title{
font-family: sans-serif;
}
#pseudocode{
background-color: rgb(254 249 195);
}
.line-number{
font-family: sans-serif;
font-size: 10px;
}
.line-number:after{
content: " ";
}
</style>