बोगोसॉर्ट क्या है?
बोगोसॉर्ट एक अत्यंत अक्षम सॉर्टिंग एल्गोरिदम है जो कलेक्शन को तब तक रैंडमली शफल करता रहता है जब तक वह सॉर्ट न हो जाए। यह परम्यूटेशन और कॉम्बिनेशन पर आधारित एक अप्रभावी एल्गोरिदम है, इसलिए इसे परम्यूटेशन सॉर्ट के नाम से भी जाना जाता है। इसके अन्य नाम हैं: शॉटगन सॉर्ट, स्टुपिड सॉर्ट, मंकी सॉर्ट, या स्लो सॉर्ट।
Input: 5 3 4 2 1 Output: 1 2 3 4 5
व्याख्या
बोगोसॉर्ट में, सरणी में असॉर्टेड तत्व होते हैं। यह जांचता है कि सरणी के तत्व क्रम में हैं या नहीं। यदि नहीं हैं, तो यह तत्वों की स्थिति को रैंडमली स्वैप करके बदल देता है, और इस प्रक्रिया को तब तक दोहराता है जब तक सरणी सॉर्ट न हो जाए।
एल्गोरिदम
bogoSort(array, n)
Begin
while array is not sorted
shuffle array
done
End
उदाहरण
#include <iostream>
#include <stdlib.h>
using namespace std;
bool is_sorted(int *arr, int n) {
while (--n >= 1) {
if (arr[n] < arr[n-1]) {
return false;
}
}
return true;
}
void shuffle(int *arr, int n) {
int temp, r;
for(int i = 0; i < n; i++) {
temp = arr[i];
r = rand() % n;
arr[i] = arr[r];
arr[r] = temp;
}
}
void bogosort(int *arr, int n) {
while (!is_sorted(arr, n)) {
shuffle(arr, n);
}
}
int main() {
int arr[] = {5, 3, 4, 2, 1};
int n = 5;
bogosort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << "\t";
}
return 0;
}आउटपुट
1 2 3 4 5
जटिलता विश्लेषण
- समय जटिलता: O((n+1)!) - अत्यंत धीमा
- स्थान जटिलता: O(1)
- व्यावहारिक उपयोग: केवल शैक्षिक उद्देश्यों के लिए
नोट: बोगोसॉर्ट का वास्तविक अनुप्रयोगों में कभी उपयोग नहीं किया जाना चाहिए क्योंकि इसकी समय जटिलता फैक्टरियल है।
