พิมพ์กรณีที่อัลกอริทึมจัดเรียงล้มเหลวใน 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 ตรวจสอบและสลับค่าที่ไม่เรียงลำดับ

การวิเคราะห์

อัลกอริทึมนี้จะล้มเหลวเมื่อข้อมูลเรียงจากมากไปน้อย (reverse order) นอกจากนี้จะหาคำตอบได้เฉพาะเมื่อ n ≤ 2 เท่านั้น

เช่น n = 5 → Output: 5 4 3 2 1  Time complexity: 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 << "The case in which the algorithm goes invalid for " << n << " element array is:\n";
    invalidCase(n);
    return 0;
}

ผลลัพธ์ (Output)

The case in which the algorithm goes invalid for 6 element array is:
6 5 4 3 2 1