Bogosort chỉ cần xáo trộn một bộ sưu tập một cách ngẫu nhiên cho đến khi nó được sắp xếp. BogoSort là một thuật toán hoán vị và kết hợp không hiệu quả, đó là lý do tại sao nó được gọi là Sắp xếp hoán vị. BogoSort là kỹ thuật sắp xếp rất flop còn được gọi là phân loại súng ngắn, sắp xếp ngu ngốc, sắp xếp khỉ hoặc sắp xếp chậm . Thuật toán tạo liên tiếp các hoán vị đầu vào của nó cho đến khi nó tìm thấy một hoán vị được sắp xếp.
Input - 53421 Output - 12345
Giải thích
Trong mảng bogosort sẽ bao gồm phần tử chưa được sắp xếp kiểm tra xem các phần tử của mảng có theo thứ tự hay không, và nếu không, sau đó thay đổi vị trí của các phần tử mảng, bằng cách hoán đổi các phần tử một cách ngẫu nhiên và lặp lại quá trình cho đến khi mảng được sắp xếp.
Ví dụ
#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";
}
}