In trường hợp thuật toán sắp xếp đã cho không thành công trong C ++

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

Thuật toá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])

Hãy xem xét thuật toán sắp xếp này, nó đang sử dụng hai vòng lặp lồng nhau. Vòng ngoài sẽ bắt đầu từ 1 đến n-1 và vòng trong từ i đến n-1, đồng thời sẽ kiểm tra giá trị của phần tử vòng lặp bên trong và các phần tử vòng ngoài ở mỗi lần lặp và hoán đổi các phần tử không theo thứ tự.

Vì vậy, thuật toán này sẽ thất bại trong trường hợp các phần tử được sắp xếp theo thứ tự ngược lại. Ngoài ra, chúng ta chỉ có thể tìm ra giải pháp khi n <=2.

So, for n = 5.
Output : 5 4 3 2 1
Time complexity − O(N)

Ví dụ

Mã để hiển thị việc triển khai giải pháp của chúng tôi

#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;
}

Đầu ra

Trường hợp thuật toán không hợp lệ cho mảng 6 phần tử là -

6 5 4 3 2 1