Insertion Sort
挿入ソート
Outline
挿入ソートとは、ある値を何処に入れるべきか、という決定要素に
基づくソートアルゴリズムである.
これはよく、トランプで手札のカードを順に並べることに例えられる.
Program
サイズnの配列dataに対して挿入ソートを行う関数.
void insertion_sort(int data[], int n) {
int v, j;
for(int i = 1 ; i < n ; i++) {
v = data[i];
j = i;
while(j > 0 && data[j - 1] > v) {
data[j] = data[j - 1];
j--;
}
data[j] = v;
}
}Consideration
#mimetex( \Theta(n^2) )