इस समस्या में, हमें एक सॉर्टिंग एल्गोरिदम और एक संख्या 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 ≤ 2 हो।
इसलिए, n = 5 के लिए। आउटपुट: 5 4 3 2 1 टाइम कॉम्प्लेक्सिटी - O(N)
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने वाला कोड:
#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;
}
आउटपुट
The case in which the algorithm goes invalid for 6 element array is -
6 5 4 3 2 1
