![挿入ソートの実装例
void insertion_sort(int *data, size_t N) {
for (size_t i = 1; i < N; ++i) {
int value = data[i];
size_t j = i;
for ( ; (j > 0) && (value < data[j – 1]); --j)
data[j] = data[j – 1];
data[j] = value;
}
}
2014年1月18日
挿入ソート
4](https://image.slidesharecdn.com/2014-01-18insertionsort-140117144732-phpapp01/85/-4-320.jpg)
![番兵による効率化
? if (value < data[0])
– すべての要素を後ろにずらす
– ループ条件から “value < data[j – 1]” がなくなる
? else
– data[0] が番兵に挿入位置を探す
– ループ条件から “j > 0” がなくなる
? 参考資料
– STL の実装（/usr/include/c++/bits/stl_algo.h）
2014年1月18日
挿入ソート
5](https://image.slidesharecdn.com/2014-01-18insertionsort-140117144732-phpapp01/85/-5-320.jpg)
![挿入ソートの実装例（番兵あり）
void sort_1(int *data, size_t N) {
for (size_t i = 1; i < N; ++i) {
int value = data[i];
size_t j = i;
if (value < data[0]) {
for ( ; j > 0; --j) // ループが単純になった
data[j] = data[j – 1];
} else {
for ( ; value < data[j - 1]; --j) // ループが単純になった
data[j] = data[j – 1];
}
data[j] = value;
}
}
2014年1月18日
挿入ソート
6](https://image.slidesharecdn.com/2014-01-18insertionsort-140117144732-phpapp01/85/-6-320.jpg)
![部分ソートの実装例
void partial_sort(int *data, size_t N, size_t M) {
insertion_sort(data, M);
for (size_t i = M; i < N; ++i) {
int value = data[i];
if (value >= data[M – 1])
continue;
data[i] = data[M – 1];
size_t j = M - 1;
for ( ; (j > 0) && (value < data[j - 1]); --j)
data[j] = data[j – 1];
data[j] = value;
}
}
2014年1月18日
挿入ソート
12](https://image.slidesharecdn.com/2014-01-18insertionsort-140117144732-phpapp01/85/-12-320.jpg)
![番兵による効率化（再掲）
? if (value < data[0])
– すべての要素を後ろにずらす
– ループ条件から “value < data[j – 1]” がなくなる
? else
– data[0] が番兵に挿入位置を探す
– ループ条件から “j > 0” がなくなる
? 参考資料
– STL の実装（/usr/include/c++/bits/stl_algo.h）
2014年1月18日
挿入ソート
13](https://image.slidesharecdn.com/2014-01-18insertionsort-140117144732-phpapp01/85/-13-320.jpg)
挿入ソート
- 2. 挿入ソートとは K 個目までの要素が整列済みのとき 整列状態が維持されるように K + 1 個目の要素を挿入する 初期状態 K = 0 として すべての要素を挿入するまで 上記の操作を繰り返す 2014年1月18日 挿入ソート 2
- 3. 挿入ソートの実行例 ? 入力データ列（N = 5） – 初期状態 59 13 37 5 79 59 13 37 5 79 13 59 37 5 79 13 37 59 5 79 5 13 37 59 79 5 13 37 59 79 ? 整列手順 – 59 を挿入 – 13 を挿入 – 37 を挿入 – 5 を挿入 – 79 を挿入 – 完了 2014年1月18日 挿入ソート 3
- 4. 挿入ソートの実装例 void insertion_sort(int *data, size_t N) { for (size_t i = 1; i < N; ++i) { int value = data[i]; size_t j = i; for ( ; (j > 0) && (value < data[j – 1]); --j) data[j] = data[j – 1]; data[j] = value; } } 2014年1月18日 挿入ソート 4
- 5. 番兵による効率化 ? if (value < data[0]) – すべての要素を後ろにずらす – ループ条件から “value < data[j – 1]” がなくなる ? else – data[0] が番兵に挿入位置を探す – ループ条件から “j > 0” がなくなる ? 参考資料 – STL の実装（/usr/include/c++/bits/stl_algo.h） 2014年1月18日 挿入ソート 5
- 6. 挿入ソートの実装例（番兵あり） void sort_1(int *data, size_t N) { for (size_t i = 1; i < N; ++i) { int value = data[i]; size_t j = i; if (value < data[0]) { for ( ; j > 0; --j) // ループが単純になった data[j] = data[j – 1]; } else { for ( ; value < data[j - 1]; --j) // ループが単純になった data[j] = data[j – 1]; } data[j] = value; } } 2014年1月18日 挿入ソート 6
- 7. 挿入ソートの特徴 ? 時間計算量 – 要素数を N として O(N2) ? N が大きいときは危険 – 入力データ列が整列済みであれば O(N) ? これを期待して使うのは危険 ? 使いどころ – N が小さければ高速 ? クイックソートの仕上げに使うことが多い 2014年1月18日 挿入ソート 7
- 9. 部分ソートとは データ列の先頭 M 個の要素が 上位 M 個の要素を 整列した結果となるように並べ替える それ以外の要素の順序は問わない 2014年1月18日 挿入ソート 9
- 10. 挿入ソートによる部分ソート ? 手順 – 先頭 M 個の要素を整列する – M + 1 個目から N 個目は以下のように操作する ? M 個目の要素以上なら何もしない ? そうでなければ整列状態が維持されるように挿入する ? 時間計算量 – O(M?N) ? M が小さければ高速 2014年1月18日 挿入ソート 10
- 11. 部分ソートの実行例 ? 入力データ列（N = 7） – 初期状態 79 13 53 37 97 29 5 13 53 79 37 97 29 5 13 37 53 79 97 29 5 13 37 53 79 97 29 5 13 29 37 79 97 53 5 5 13 29 79 97 53 37 ? 整列手順（M = 3） – 初期整列 – 37 を挿入 – 79 を挿入 – 29 を挿入 – 5 を挿入 – 完了 2014年1月18日 挿入ソート 11
- 12. 部分ソートの実装例 void partial_sort(int *data, size_t N, size_t M) { insertion_sort(data, M); for (size_t i = M; i < N; ++i) { int value = data[i]; if (value >= data[M – 1]) continue; data[i] = data[M – 1]; size_t j = M - 1; for ( ; (j > 0) && (value < data[j - 1]); --j) data[j] = data[j – 1]; data[j] = value; } } 2014年1月18日 挿入ソート 12
- 13. 番兵による効率化（再掲） ? if (value < data[0]) – すべての要素を後ろにずらす – ループ条件から “value < data[j – 1]” がなくなる ? else – data[0] が番兵に挿入位置を探す – ループ条件から “j > 0” がなくなる ? 参考資料 – STL の実装（/usr/include/c++/bits/stl_algo.h） 2014年1月18日 挿入ソート 13
- 14. 順位指定による部分ソート ? 順位指定とは – 上位 M 個の代わりに上位 M 位までを整列する ? 実装方法 – 上位 M 位に含まれる要素の数を維持する – 面倒なので詳細は省略 ? 時間計算量 – O(M?N) 2014年1月18日 挿入ソート 14
- 15. おわりに ? 使いどころについて – 小規模なデータ列に強い ? 連携について – マージソートの初期段階にも使える ? 部分ソートについて – アイデアはほかの整列アルゴリズムでも使える – ヒープソートの方が大きな M に対応できる 2014年1月18日 挿入ソート 15