C++での挿入ソートの時間計算量の質問

挿入ソートの時間計算量はどれくらいですか？

時間計算量 入力量の関数として処理または実行するために一連のコードまたはアルゴリズムにかかる時間です。

挿入ソートの場合、時間計算量はO（n）のオーダーです。つまり、最良のシナリオではnの大きなOです。また、平均的または最悪のシナリオでは、複雑さはO（n ² のオーダーです。 。

挿入ソートアルゴリズムを次の形式のnサイズの配列に適用すると、ソートの時間計算量はどうなりますか：6、5、8、7、10、9……I、i-1

上記の配列をソートするフォームの時間計算量はO（n）です。このアルゴリズムを注意深く見てみましょう。ここでは、すべてのペアが元の位置から交換されます。つまり、要素1と要素2の位置が交換され、3と4が交換されます。したがって、アルゴリズムの並べ替え中に、このアルゴリズムを並べ替えるのに必要な操作はn回だけです。

挿入ソートを定義し、挿入ソートのコードを記述しますか？

挿入ソートは、ソートされた配列内のその位置に要素を配置することによってデータ構造をソートするソートアルゴリズムです。

以下のコードは、挿入ソートの関数を示しています-

例

void insertionSort(int arr[], int n) {
   for (int i = 1; i < n; i++){
      int element = arr[i];
      int j = i-1;
      while (j >= 0 && arr[j] > element){
         arr[j+1] = arr[j];
         j = j-1;
      }
      arr[j+1] = element;
   }
}