โปรแกรม C++ สำหรับ BogoSort หรือ Permutation Sort

Bogosort เรียงลำดับโดยการสับเปลี่ยนชุดข้อมูลแบบสุ่มจนกว่าจะเรียงลำดับได้ BogoSort เป็นอัลกอริทึมที่ไม่มีประสิทธิภาพซึ่งขึ้นอยู่กับการเรียงสับเปลี่ยนและการจัดหมู่ ดังนั้นจึงเรียกว่า Permutation Sort BogoSort เป็นเทคนิคการเรียงที่ล้มเหลวมาก ซึ่งรู้จักในชื่ออื่นๆ เช่น Shotgun Sort, Stupid Sort, Monkey Sort หรือ Slow Sort อัลกอริทึมนี้สร้างการเรียงสับเปลี่ยนของอินพุตซ้ำๆ จนกว่าจะพบลำดับที่ถูกต้อง

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";
    }
}