アルゴリズムとデータ構造：単純挿入ソート

単純挿入ソートはほとんど整列が終わっているデータに対して効率が良い。
安定ソート。内部ソート。基本挿入法ともいう。

[平均計算時間]
O(n2)

[最悪計算時間]
O(n2)

[insertion_sort.c]

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10 /* データ件数 */

int sort[N];
int count;

void InsertSort(void);
void output(void);

void InsertSort(void){
    int i, sorted, temp, insert;

    for(sorted=0; sorted < N - 1; sorted++){
        insert = sort[sorted + 1];
        
        for(i=0; i<=sorted; i++){
            if(sort[i] > insert){
                break; 
            } 
            ++count;
        }

        while(i <= sorted + 1){
            temp = sort[i];
            sort[i] = insert;
            insert = temp;
            i++;
        }
        output();
    }
}

int main(void){
    int i;
    clock_t start,end;
    
    srand((unsigned int) time(NULL));
    for(i=0; i< N; i++){
        sort[i]  = rand() % 10 + 1;
    }

    printf("Stundy...\n");
    output();

    printf("Start...\n");
    start = clock();
    InsertSort();
    end = clock();
    printf("End...\n");
    output();
    printf("Count:%d\n",count);
    printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC);

    return EXIT_SUCCESS;
}

void output(void){
    int i;
    printf("sort => [");
    for(i=0; i<N; i++){
        printf("%d,",sort[i]); 
    }
    printf("]\n");
}

データ10件の実行結果

$ ./insertion_sort 
Stundy...
sort => [9,8,8,5,3,3,10,2,3,7,]
Start...
sort => [8,9,8,5,3,3,10,2,3,7,]
sort => [8,8,9,5,3,3,10,2,3,7,]
sort => [5,8,8,9,3,3,10,2,3,7,]
sort => [3,5,8,8,9,3,10,2,3,7,]
sort => [3,3,5,8,8,9,10,2,3,7,]
sort => [3,3,5,8,8,9,10,2,3,7,]
sort => [2,3,3,5,8,8,9,10,3,7,]
sort => [2,3,3,3,5,8,8,9,10,7,]
sort => [2,3,3,3,5,7,8,8,9,10,]
End...
sort => [2,3,3,3,5,7,8,8,9,10,]
Count:16
Time:0.00

データ1万件の実行結果

$ ./insertion_sort 
Stundy...
Start...
End...
Count:27529798
Time:0.24

データ100万件にしたらレスポンスは返ってこなかった。

PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND                                                                                       
20931 dela      25   0  7576 4260  292 R 100.0  0.8   2:40.77 insertion_sort