Insertion Sort (插入排序)

Sorting Problem

Input: A sequence of n numbers { $a_0, a_1, ... , a_{n-1}$}

Output: A permutation (reordering) { $a'_0, a'_1, ... , a'_{n-1}$} of the input sequence such that $a'_0 \leq a'_1 \leq ... \leq a'_{n-1}$

Algorithm

An algorithm is a sequence of computational steps that transform the input into the output.

Insertion Sort 概念

Insertion Sort 和打撲克牌時，從牌桌上逐一拿起撲克牌，在手上排序的過程相同。

舉例

Input: {5 2 4 6 1 3}。

首先拿起第一張牌, 手上有 {5}。

拿起第二張牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。

拿起第三張牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。

以此類推。

Insertion Sort 演算法概念

Input: {A[0], A[1], ... ,A[n-1]}

Index j 代表目前要 insert 到手上的牌。

j iterate thru 1 to n-1

在各個 iteration 之前，{A[0], A[1], ... A[j-1]} 是 sorted。

在各個 iteration 完成後，{A[0], A[1], ... A[j-1], A[j]} 是 sorted。

這樣的 algorithm design technique 稱之為 incremental approach (遞增法)。

C++ implementation (in-place sorting)

	#include <iostream>
	#include <vector>
	using namespace std;
	void printArray(vector<int> &vec)
	{
	for (int i=0; i<vec.size(); i++)
	cout << vec[i] << " ";
	cout << endl;
	}
	void insertionSort(vector<int> &vec)
	{
	for (int j = 1; j < vec.size(); j++) {
	int key = vec[j];
	// Insert vec[j] into the sorted sequence vec[0...j-1]
	int i = j - 1;
	while ((i >= 0) && (vec[i] > key)) {
	vec[i+1] = vec[i];
	i--;
	}
	vec[i+1] = key;
	}
	}
	int main(int argc, char** argv) {
	int array1[] = {5, 2, 4, 1, 9, 3, 6};
	vector<int> vec1(array1, array1+sizeof(array1)/sizeof(int));
	cout << "original array: " << endl;
	printArray(vec1);
	insertionSort(vec1);
	cout << "sorted array: " << endl;
	printArray(vec1);
	return 0;
	}

view raw InsertionSort.cpp hosted with ❤ by GitHub

Performance Analysis

Worst case performance: $O(n^2)$

worst case: array 反向排序 (數字由大到小排序)。

loop 被執行的次數: $\sum_{j=1}^{n-1} j = \frac{(n-1)*n}{2}$

running time: $O(n^2)$

Average case performance: $O(n^2)$

平均而言，loop 被執行的次數: $\sum_{j=1}^{n-1} \frac{j}{2} = \frac{(n-1)*n}{2*2}$

running time: $O(n^2)$

Best case performance: $O(n)$

best case: array 已排序完成 (數字由小到大排序)。

loop 被執行的次數: $\sum_{j=1}^{n-1} 1 = n-1$

running time: $O(n)$

Space complexity: $O(1)$ auxiliary

此 in-place 演算法並沒有隨著 array length 額外需要 space, 因此 space complexity 是 $O(1)$ auxiliary。

延伸閱讀

[書籍] Introduction to Algorithms, 3rd. edition - Chap 2

[WiKi] 插入排序

[WiKi] Insertion sort

系列文章

Insertion Sort (插入排序)

Merge Sort (合併排序)

Heapsort (堆積排序)