Bogosort จะสุ่มคอลเลคชันแบบสุ่มจนกว่าจะจัดเรียง BogoSort เป็นอัลกอริธึมที่ไม่มีประสิทธิภาพตามการเรียงสับเปลี่ยนและการรวมเข้าด้วยกัน นั่นคือสาเหตุที่รู้จักการเรียงลำดับการเรียงสับเปลี่ยน BogoSort เป็นเทคนิคการจัดเรียงที่ล้มเหลวอย่างมาก ซึ่งเรียกอีกอย่างว่า การจัดเรียงปืนลูกซอง การจัดเรียงแบบโง่ การจัดเรียงลิง หรือการจัดเรียงแบบช้า . อัลกอริทึมจะสร้างการเรียงสับเปลี่ยนของอินพุตอย่างต่อเนื่องจนกว่าจะพบรายการที่จัดเรียง
Input - 53421 Output - 12345
คำอธิบาย
ในอาร์เรย์ Bogosort จะประกอบด้วยองค์ประกอบที่ไม่เรียงลำดับซึ่งตรวจสอบว่าองค์ประกอบอาร์เรย์อยู่ในลำดับหรือไม่ และหากไม่ใช่ ให้เปลี่ยนตำแหน่งขององค์ประกอบอาร์เรย์โดยสลับองค์ประกอบแบบสุ่ม และทำซ้ำขั้นตอนจนกว่าจะจัดเรียงอาร์เรย์
ตัวอย่าง
#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";
}
} 