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

ที่นี่เราจะดูอัลกอริทึมการเรียงอีกตัวหนึ่งชื่อ Bogo Sort การเรียงนี้รู้จักในชื่อ Permutation sort, Stupid sort, slow sort เป็นเทคนิคการเรียงที่ไม่มีประสิทธิภาพโดยเฉพาะ อยู่ใน paradigm ของ generate and test (สร้างและทดสอบ) มันสร้างการเรียงสับเปลี่ยนซ้ำๆ จนกว่าจะเรียงแล้ว แนวคิดตรงไปตรงมา จนกว่ารายการจะเรียงแล้ว ให้สับเปลี่ยนองค์ประกอบ

อัลกอริทึม

bogoSort(array, n)

Begin
    while the arr is not sorted, do
        shuffle arr
    done
End

ตัวอย่าง

#include<iostream>
#include<cstdlib>
using namespace std;

bool isSorted(int arr[], int n) {
    // check whether the list is sorted or not
    while (--n > 1)
        if (arr[n] < arr[n - 1])
            return false;
    return true;
}

void shuffle(int arr[], int n) {
    for (int i = 0; i < n; i++)
        swap(arr[i], arr[rand() % n]);
}

void bogoSort(int arr[], int n) {
    while (!isSorted(arr, n))
        shuffle(arr, n);
}

int main() {
    int data[] = {54, 74, 98, 5, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data) / sizeof(data[0]);
    cout << "Sorted Sequence ";
    bogoSort(data, n);
    for(int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
}

ผลลัพธ์

Sorted Sequence 5 13 20 32 35 40 54 74 98 98