বোগোসর্ট একটি সংগ্রহকে র্যান্ডমলি শাফল করে সর্ট হওয়া পর্যন্ত চালিয়ে যায়। বোগোসর্ট পারমুটেশন এবং কম্বিনেশন ভিত্তিক একটি অকার্যকর অ্যালগরিদম, তাই এটিকে পারমুটেশন সর্ট বলা হয়। এটি একটি ব্যর্থ সর্টিং কৌশল যা শটগান সর্ট, স্টুপিড সর্ট, মাঙ্কি সর্ট বা স্লো সর্ট নামে পরিচিত। অ্যালগরিদমটি তার ইনপুটের পারমুটেশন ক্রমাগতভাবে তৈরি করে যতক্ষণ না একটি সর্টেড অ্যারে পাওয়া যায়।
ইনপুট - 53421 আউটপুট - 12345
ব্যাখ্যা
বোগোসর্টে অ্যারে অসর্টেড উপাদান নিয়ে গঠিত হয়। অ্যারে উপাদানগুলো ক্রমবদ্ধ কিনা তা চেক করা হয়, যদি না হয় তবে উপাদানগুলোর অবস্থান র্যান্ডমলি সোয়াপ করে বদলানো হয়, এবং অ্যারে সর্ট না হওয়া পর্যন্ত এই প্রক্রিয়াটি পুনরাবৃত্তি করা হয়।
উদাহরণ
#include <iostream>
#include <stdlib.h>
using namespace std;
int is_sorted(int *arr, int n) {
while (--n >= 1) {
if (arr[n] < arr[n-1]) {
return 0;
}
}
return 1;
}
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 i;
bogosort(arr, 5);
for (i = 0; i < 5; i++) {
cout << arr[i] << "\t";
}
}
