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까지 순회하면서 각 반복마다 내부 루프의 요소와 외부 루프의 요소 값을 비교하여 순서가 맞지 않는 요소들을 교환(swap)합니다.

그런데 이 알고리즘에는 치명적인 약점이 있습니다. 바로 요소들이 역순(내림차순)으로 정렬되어 있는 경우입니다. 이런 입력이 들어오면 알고리즘은 배열을 올바르게 정렬하지 못하고 실패하게 됩니다.

또한 중요한 점은, n이 2 이하일 때는 어떤 배열을 만들어도 알고리즘이 실패하는 경우를 만들 수 없다는 것입니다. 따라서 유효한 반례는 n이 3 이상일 때만 존재합니다.

해결 방법

알고리즘이 실패하는 가장 간단한 반례는 역순으로 정렬된 배열입니다. 예를 들어 n = 5인 경우 다음과 같은 출력을 얻을 수 있습니다.

입력 크기 : n = 5
출력 : 5 4 3 2 1
시간 복잡도 : O(N)

구현 예제

다음은 위 해결 방법을 구현한 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<<"" <<n<<"개 요소를 가진 배열에서 알고리즘이 실패하는 경우 :\n";
    invalidCase(n);
    return 0;
}

실행 결과

6개의 요소를 가진 배열에서 알고리즘이 실패하는 경우는 다음과 같습니다.

6 5 4 3 2 1

이처럼 내림차순으로 정렬된 배열을 입력으로 제공하면 해당 정렬 알고리즘은 올바른 결과를 내지 못합니다. 코드의 시간 복잡도는 단순히 n부터 1까지 숫자를 출력하므로 O(N)으로 매우 효율적입니다.