C++ STLを使った挿入ソートの実装方法を解説

この記事では、C++のSTL（標準テンプレートライブラリ）を活用して挿入ソートを実装する方法を解説します。

従来の挿入ソートでは、未ソート部分の要素を一つずつ比較しながら適切な位置へ移動させますが、STLを利用することでこの処理をより簡潔に記述できます。具体的には、std::upper_boundで正しい挿入位置を特定し、std::rotateで配列の未ソート部分を回転させて整列させます。

挿入ソートの仕組み

挿入ソートは、配列を「ソート済み部分」と「未ソート部分」に分けて考えるアルゴリズムです。未ソート部分から先頭の要素を取り出し、ソート済み部分の中で正しい位置に挿入する操作を繰り返します。

• std::upper_bound：ソート済み範囲内で、指定した値より大きい最初の要素を指すイテレータを返します。これにより挿入位置が分かります。
• std::rotate：指定した範囲の要素を回転させます。ここでは、挿入位置から現在の要素までを1つ右にずらす役割を果たします。

サンプルコード

#include <bits/stdc++.h>
// 挿入ソートを実行する関数
void insertionSort(std::vector<int> &vec){
   for (auto it = vec.begin(); it != vec.end(); it++){
      auto const insertion_point =
      std::upper_bound(vec.begin(), it, *it);
      std::rotate(insertion_point, it, it+1);
   }
}
// 配列を出力する関数
void print(std::vector<int> vec){
   for( int x : vec)
   std::cout << x << " ";
   std::cout << '\n';
}
int main(){
   std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};
   insertionSort(arr);
   print(arr);
   return 0;
}

実行結果

1 2 3 4 5 5 6 7

コードの解説

insertionSort関数

ベクタの各要素に対して反復処理を行い、現在の要素*itより大きい値が最初に現れる位置をstd::upper_boundで求めます。その後、std::rotateを使って挿入位置から現在位置までの範囲を回転させることで、要素を正しい位置へ移動させています。

print関数

範囲ベースforループを使用し、ソート後の配列の全要素をスペース区切りで出力します。

main関数

順序がバラバラの整数ベクタを用意し、insertionSortでソートした後、printで結果を表示しています。

まとめ

STLのstd::upper_boundとstd::rotateを組み合わせることで、挿入ソートを短く読みやすいコードで実装できます。二分探索によって挿入位置を特定できるため、比較回数も抑えられ、効率的な動作が期待できます。