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. To make this list more interesting, we are only going to consider the algorithms in which play a role in the sorting process. That is, there won't be algorithms that use a wait function or an infinite loop.

Bogosort

-This may be the most famous bad sorting algorithm. Its legendary strategy consists of randomly shuffling and array until it is sorted.

#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.

Complexity

• In average, $$$(N-1)*N!$$$ swaps are made.

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

Slowsort

-This algorithm is a very interesting one. It utilizes the parody technique multiply and surrender in order to sort its elements. The recursion it utilizes is very efficient and interesting:

function slowsort(begin,end)

   mid = floor((begin + end)/2)
   slowsort(begin,mid)
   slowsort(mid + 1, end)
   if(array[mid] > array[end]) swap(array[mid],array[end]) //we compare the greatest element of each half
   //now, the greatest element of the array is in the end, so we call recursively without including the last element

   slowsort(begin,end - 1)

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

vector<int> v = {10,9,8,7,6,5,4,3,2,1};

void slowsort(int st, int ed)
{
    if(st >= ed) return;

    int mid = (st + ed)/2;

    slowsort(st,mid);
    slowsort(mid + 1, ed);

    if(v[mid] > v[ed]) swap(v[mid],v[ed]);

    slowsort(st,ed - 1);
}

int main()
{
    slowsort(0,v.size() - 1);

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