C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++STLを使用した挿入ソート

このチュートリアルでは、C++STLを使用して挿入ソートを理解するためのプログラムについて説明します。

ここでは、std ::upper_boundを使用して間違った位置にある要素を見つけ、配列の並べ替えられていない部分を回転させて並べ替えます。

例 
#include <bits/stdc++.h>
//function to perform insertion sort
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);
   }
}
//printing the array
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

  1. 挿入ソートを実装するC++プログラム

    このソート手法はカードソート手法と似ています。つまり、挿入ソートメカニズムを使用してカードをソートします。この手法では、データセットから1つの要素を取得し、データ要素をシフトして、取得した要素をデータセットに挿入し直す場所を作成します。 挿入ソート手法の複雑さ 時間計算量：最良の場合はO（n）、平均および最悪の場合はO（n2） スペースの複雑さ：O（1） Input − The unsorted list: 9 45 23 71 80 55 Output − Array after Sorting: 9 23 45 55 71 80 アルゴリズム in

  2. C++STLを使用したカスタムオブジェクトのベクトルの並べ替え

    C++STL関数std::sortを使用して、カスタムオブジェクトのベクトルを並べ替えることができます。ソート関数には、最初、最後、コンパレータを引数として取るオーバーロードされた形式があります。最初と最後は、コンテナの最初と最後の要素へのイテレータです。コンパレータは、コンテナのソート方法を指示するために使用できる述語関数です。 例 #include<iostream> #include<algorithm> #include<vector> using namespace std; struct MyStruct {    int