ソートアルゴリズムセット-3

7.ソート・チャートの挿入
挿入ソートの最適な実行時間はO(n)であり,既にソートされている場合,平均が最もO(n 2)であるため,ランダムな未ソートデータを処理する際には良いアルゴリズムではない.
各新しい要素を並べ替えられた要素と比較し、正しい位置に挿入することで、トランプをするように、新しいカードを手に入れて並べ替えられた真ん中に並べ替えられた配列を作成します.
挿入ソートは安定したその場ソートアルゴリズムであり、特に小さなデータセットをソートするのに適しており、通常は他のより複雑なソートアルゴリズムの構築モジュールとして機能する.

void insertionSort(int *a, int len) {
    for (int which=1; which<len; which++) {
        int val = a[which];
        for (int i=0; i<which; i++) {
            if (a[i] > val) {
                // do shift to 
                for (int j=which; j>i; j--) {
                    a[j] = a[j-1];
                }
                a[i] = val;
                break;
            }
        }
    }
}

8.ビットソートBit Sort
整数ビットの各ビットで1つの数字を表します.『プログラミング珠玉』を詳しく参考にします.

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }

int main(void)
{ 
    int i;
    for (i = 0; i < N; i++)
        clr(i);

    while (scanf("%d", &i) != EOF)
        set(i);

    for (i = 0; i < N; i++)
        if (test(i))
            printf("%d
", i);

    return 0;
}