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

単純挿入ソートの改良版。単純挿入ソートでは挿入箇所をリニアサーチで探していた。
2分挿入ソートではバイナリサーチで挿入箇所を探している。
データ数が大きい場合に効率的。

[計算量]
O(n2)

[binary_insert_sort.c]

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

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

int sort[N];
int count;
void BinaryInsertSort(void);
void output(void);

void BinaryInsertSort(void){
    int i, sorted, temp, insert;
    int left, mid, right;

    for(sorted = 1; sorted < N; sorted++){
        insert = sort[sorted]; 

        left = 0;
        right = sorted;
        while(left < right){
            mid = (left + right)  / 2;

            if(sort[mid] < insert){
                left = mid + 1; 
            }
            else{
                right = mid; 
            }
            ++count;
        }

        printf("insert:%d,left:%d \n",insert,left);

        i = left;
        while(i <= sorted){
            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();
    BinaryInsertSort();
    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件の実行結果

./binary_insert_sort 
Stundy...
sort => [10,2,5,9,3,3,6,10,4,6,]
Start...
insert:2,left:0 
sort => [2,2,5,9,3,3,6,10,4,6,]
sort => [2,10,5,9,3,3,6,10,4,6,]
insert:5,left:1 
sort => [2,5,5,9,3,3,6,10,4,6,]
sort => [2,5,10,9,3,3,6,10,4,6,]
insert:9,left:2 
sort => [2,5,9,9,3,3,6,10,4,6,]
sort => [2,5,9,10,3,3,6,10,4,6,]
insert:3,left:1 
sort => [2,3,9,10,3,3,6,10,4,6,]
sort => [2,3,5,10,3,3,6,10,4,6,]
sort => [2,3,5,9,3,3,6,10,4,6,]
sort => [2,3,5,9,10,3,6,10,4,6,]
insert:3,left:1 
sort => [2,3,5,9,10,3,6,10,4,6,]
sort => [2,3,3,9,10,3,6,10,4,6,]
sort => [2,3,3,5,10,3,6,10,4,6,]
sort => [2,3,3,5,9,3,6,10,4,6,]
sort => [2,3,3,5,9,10,6,10,4,6,]
insert:6,left:4 
sort => [2,3,3,5,6,10,6,10,4,6,]
sort => [2,3,3,5,6,9,6,10,4,6,]
sort => [2,3,3,5,6,9,10,10,4,6,]
insert:10,left:6 
sort => [2,3,3,5,6,9,10,10,4,6,]
sort => [2,3,3,5,6,9,10,10,4,6,]
insert:4,left:3 
sort => [2,3,3,4,6,9,10,10,4,6,]
sort => [2,3,3,4,5,9,10,10,4,6,]
sort => [2,3,3,4,5,6,10,10,4,6,]
sort => [2,3,3,4,5,6,9,10,4,6,]
sort => [2,3,3,4,5,6,9,10,4,6,]
sort => [2,3,3,4,5,6,9,10,10,6,]
insert:6,left:5 
sort => [2,3,3,4,5,6,9,10,10,6,]
sort => [2,3,3,4,5,6,6,10,10,6,]
sort => [2,3,3,4,5,6,6,9,10,6,]
sort => [2,3,3,4,5,6,6,9,10,6,]
sort => [2,3,3,4,5,6,6,9,10,10,]
End...
sort => [2,3,3,4,5,6,6,9,10,10,]
Count:24
Time:0.00

データ1万件の実行結果

./binary_insert_sort 
Stundy...
Start...
End...
Count:119422
Time:0.17

データ10万件の実行結果

./binary_insert_sort 
Stundy...
Start...
End...
Count:1527327
Time:18.24

データ100万件だと返ってこなかった。