With the broad availability of quick and efficient sorting algorithms, that can sort arrays in $$$O(N*logN)$$$ complexity, little space was left for the bad sorting algorithms. Because of this, I will, in this blog, explore the vast world of the bad sorting algorithms.

Bogosort

-This may be the most famous bad sorting algorithm. Its legendary strategy consists of randomly shuffling and array until it is sorted. In average, $$$(N-1)*N!$$$ swaps are made.

#include<bits/stdc++.h>
using namespace std;

vector<int> v = {10,9,8,7,6,5,4,3,2,1};
bool sorted()
{
    bool unsorted = false;

    for(int i = 1; i < v.size(); i++) if(v[i] < v[i-1])
        unsorted = true;

    return !unsorted;
}
int main()
{
    bool unsorted = false;
    while(!sorted())
        random_shuffle(v.begin(),v.end());

    for(int x : v) cout << x << " ";
}

*It is also worth mentioning that there is a variant of this algorithms that eliminates the randomness issue: Create all $$$N!$$$ possible permutations of a given array. Go through each one checking if they are ordered or not.

Bozosort

-This is another sorting algorithm that relies on randomness to be bad and the strategy it uses to sort is quite simple: If the array is not ordered, randomly select two elements of an array, swap them. The expected time complexity is a bit more complex, but on average $$$N!$$$ swaps are made.

#include<bits/stdc++.h>
using namespace std;
vector<int> v = {10,9,8,7,6,5,4,3,2,1};

bool sorted()
{
    bool unsorted = false;

    for(int i = 1; i < v.size(); i++) if(v[i] < v[i-1])
        unsorted = true;

    return !unsorted;
}
int main()
{
    srand(time(0));

    int iteration = 0;
    while(!sorted())
    {
        int i = rand() % v.size();
        int j = rand() % v.size();
        swap(v[i],v[j]);
    }

    for(int x : v) cout << x << " ";
}