In Ra Trường Hợp Thuật Toán Sắp Xếp Thất Bại Trong C++

Trong bài toán này, chúng ta được cho một thuật toán sắp xếp và một số n. Nhiệm vụ là in ra một mảng n phần tử mà thuật toán không thể sắp xếp đúng. Tức là thuật toán sẽ thất bại.

Thuật Toán

vòng lặp i từ 1 đến n-1
    vòng lặp j từ i đến n-1
    nếu a[j] > a[i+1]
        hoán đổi(a[i], a[j+1])

Thuật toán này sử dụng hai vòng lặp lồng nhau. Vòng ngoài chạy từ 1 đến n-1, vòng trong từ i đến n-1. Tại mỗi lần lặp, nó kiểm tra giá trị phần tử vòng trong và vòng ngoài và hoán đổi các phần tử không theo thứ tự.

Thuật toán này sẽ thất bại khi các phần tử được sắp xếp theo thứ tự ngược. Ngoài ra, chỉ tìm được giải pháp khi n <= 2.

#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 << "Trường hợp thuật toán thất bại cho mảng " << n << " phần tử là :\n";
    invalidCase(n);
    return 0;
}

Đầu Ra

Trường hợp thuật toán thất bại cho mảng 6 phần tử là:

6 5 4 3 2 1