美文网首页狮猿社算法
Algorithms_in_C++ bogo_sort

Algorithms_in_C++ bogo_sort

作者: 锦囊喵 | 来源:发表于2022-01-28 09:02 被阅读0次

    BOGO 排序

    BOGO 排序 又叫猴子排序,该排序算法通过随机打乱序列,试图对序列进行排序;通过不断的打乱,理论上可以实现序列的排序;但该算法基于随机打乱再进行验证,因此时间消耗上可能很快(一次打乱),也可能很慢(无限次打乱);

    以下为源代码:

    /**
     * @file
     * @brief Implementation of [Bogosort algorithm](https://en.wikipedia.org/wiki/Bogosort)
     *
     * @details
     *      In computer science, bogosort (also known as permutation sort, stupid sort, slowsort, 
     *      shotgun sort, random sort, monkey sort, bobosort or shuffle sort) is a highly inefficient 
     *      sorting algorithm based on the generate and test paradigm. Two versions of this algorithm 
     *      exist: a deterministic version that enumerates all permutations until it hits a sorted one,
     *      and a randomized version that randomly permutes its input.Randomized version is implemented here. 
     *
     * ### Algorithm
     * Shuffle the array untill array is sorted.
     *
     * @author [Deep Raval](https://github.com/imdeep2905)
     */
    #include <iostream>
    #include <algorithm>
    #include <array>
    #include <cassert>
    
    
    /**
     * @namespace sorting
     * @brief Sorting algorithms
     */
    namespace sorting {
    /**
     * Function to shuffle the elements of an array. (for reference)
     * @tparam T typename of the array
     * @tparam N length of array
     * @param arr array to shuffle
     * @returns new array with elements shuffled from a given array
     */
    template <typename T, size_t N>
    std::array <T, N> shuffle (std::array <T, N> arr) {
        for (int i = 0; i < N; i++) {
            // Swaps i'th  index with random index (less than array size)
            std::swap(arr[i], arr[std::rand() % N]);
        }
        return arr;
    }
    /**
     * Implement randomized Bogosort algorithm and sort the elements of a given array.
     * @tparam T typename of the array
     * @tparam N length of array
     * @param arr array to sort
     * @returns new array with elements sorted from a given array
     */
    template <typename T, size_t N>
    std::array <T, N> randomized_bogosort (std::array <T, N> arr) {
        // Untill array is not sorted
        while (!std::is_sorted(arr.begin(), arr.end())) {
            std::random_shuffle(arr.begin(), arr.end());// Shuffle the array
        }
        return arr;
    }
    
    }  // namespace sorting
    
    /**
     * Function to display array on screen 
     * @tparam T typename of the array
     * @tparam N length of array
     * @param arr array to display
     */
    template <typename T, size_t N>
    void show_array (const std::array <T, N> &arr) {
        for (int x : arr) {
            std::cout << x << ' ';
        }
        std::cout << '\n';
    }
    
    /**
     * Function to test above algorithm
     */
    void test() {
        // Test 1
        std::array <int, 5> arr1;
        for (int &x : arr1) {
            x = std::rand() % 100;
        }
        std::cout << "Original Array : ";
        show_array(arr1);
        arr1 = sorting::randomized_bogosort(arr1);
        std::cout << "Sorted Array : ";
        show_array(arr1);
        assert(std::is_sorted(arr1.begin(), arr1.end()));
        // Test 2
        std::array <int, 5> arr2;
        for (int &x : arr2) {
            x = std::rand() % 100;
        }
        std::cout << "Original Array : ";
        show_array(arr2);
        arr2 = sorting::randomized_bogosort(arr2);
        std::cout << "Sorted Array : ";
        show_array(arr2);
        assert(std::is_sorted(arr2.begin(), arr2.end()));
    }
    
    /** Driver Code */
    int main() {
        // Testing
        test();
        // Example Usage
        std::array <int, 5> arr = {3, 7, 10, 4, 1}; // Defining array which we want to sort
        std::cout << "Original Array : ";
        show_array(arr);
        arr = sorting::randomized_bogosort(arr); // Callling bogo sort on it
        std::cout << "Sorted Array : ";
        show_array(arr); // Printing sorted array
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:Algorithms_in_C++ bogo_sort

        本文链接:https://www.haomeiwen.com/subject/wmizhrtx.html