BOGO SORT

BOGO sort also known as stupid sort , slow sort ,monkey sort , shotgun sort and monkey sort . the name stupid is given to this sort because of its working ,

BOGO sort, short for "Bogosort," is a highly inefficient and humorously named sorting algorithm that serves more as a joke or a parody of sorting algorithms than a practical sorting method. In fact, it is often referred to as "stupid sort" precisely because of its absurdly inefficient nature.

Here's how Bogo sort works:

1. Start with an unsorted list of elements that need to be sorted.
2. Randomly shuffle the elements in the list.
3. Check if the list is sorted. If it is, stop; otherwise, go back to step 2
4. Repeat steps 2 and 3 until the list becomes sorted.

" my college pc crashes .when I run this algo on that pc for
around 1000 of data"

#include<bits/stdc++.h>

using namespace std;

bool isSorted(int Arr[], int N)

{

    for(int i=1; i<N; i++)

    {

        if(Arr[i] < Arr[i-1])

            return false;

    }

    return true;

}



void randomly_shuffle(int Arr[], int N)

{

    for(int i = 0; i < N; i++)

    {

        swap(Arr[i], Arr[rand() % N]);

    }

}




int main()

{

    int N = 4;

    int Arr[N] = {2, 13, 7, 1};



    // isSorted() function return true if array

    // is sorted else it returns false

    while(!isSorted(Arr, N))

    {

        // randomly_shuffle() function generates a

        // random permutation of array

        randomly_shuffle(Arr, N);

    }

    for(int i = 0; i < N; i++)

        cout << Arr[i] << " ";



    return 0;

}

TIME COMPLEXITY

Worst-case time complexity: O(infinite)

Average-case time complexity: O(n! * n) :- There are n! permutations, only one of which is sorted. So, we would expect to get the correct answer after about O(n!) iterations. And each shuffle/check operation is itself O(n)

Best-case time complexity: O(n)
When the given array is already sorted, the program terminates just after checking if the array is sorted once, which takes O(n) time to execute.