C++で指定されたソートアルゴリズムが失敗するケースを出力する方法

この問題では、あるソートアルゴリズムと整数 n が与えられます。私たちのタスクは、そのアルゴリズムでは正しくソートできない（つまりアルゴリズムが失敗してしまう）ような、n 個の要素からなる配列を出力することです。

対象となるアルゴリズム

loop i from 1 to n-1
    loop j from i to n-1
        if a[j] > a[i+1]
            swap(a[i], a[j+1])

このアルゴリズムは二重ループを使用しています。外側のループは 1 から n-1 まで、内側のループは i から n-1 まで繰り返し、各反復ごとに要素同士の値を比較して、順序が崩れているペアを入れ替えていく仕組みです。

一見すると正しく動作しそうに見えますが、このアルゴリズムには弱点があります。要素が降順（逆順）に並んでいる場合に正しくソートできず、失敗してしまうのです。

さらに、そのような「失敗ケース」となる配列が存在するのは n ≥ 3 のときだけです。n ≤ 2 の場合はどのような入力を与えてもアルゴリズムが破綻することはないため、その場合は -1 を出力します。

失敗ケースの出力方法

答えは非常にシンプルで、n から 1 へと降順に並べた配列をそのまま出力すればよいだけです。

例：n = 5 の場合
出力：5 4 3 2 1
時間計算量：O(N)

C++での実装例

以下は、上記の解法を実装した C++ のコードです。

#include <iostream>
using namespace std;
void invalidCase(int n) {
    if (n <= 2) {
        cout << -1;
        return;
    }
    for (int i = n; i >= 1; i--)
        cout<<i<<" ";
}
int main() {
    int n = 6;
    cout<<"The case in which the algorithm goes invalid for "<<n<<" element array is :\n";
    invalidCase(n);
    return 0;
}

出力結果

6 要素の配列に対して、このアルゴリズムが失敗するケースは次のとおりです。

6 5 4 3 2 1