With the broad availability of quick and efficient sorting algorithms, that can sort arrays in $$$O(N*logN)$$$ complexity, little attention has been given to the vast and interesting world of the bad sorting algorithms. Because of this, I will, in this blog, explore this area. 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(!is_sorted(v.begin(),v.end()))
        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};

int main()
{
    srand(time(0));

    int iteration = 0;
    while(!is_sorted(v.begin(),v.end()))
    {
        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 infamous technique of 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 << " ";
}

Complexity

• The complexity of this method is kinda sketchy, so I will just say it is very very bad (not polynomial, not by far).

To finish this amazing list, I will present a sorting algorithm that becomes faster the more faith one has. I present to you the unmatched, the most amazing:

Miracle Sort

This niche method relies solely on the faith the programmer has on whatever it is that he believes. The method to sort consists of 3 simple steps:

1. Check if the array is sorted
2. Have faith
3. Check if, by some miracle, the array is sorted again

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

void pray()
{
    //put whatever you use to pray here, I will put my prayer
    /*
	ヴァスコ・ダ・ガマ賛歌
	ヴァスコ・ダ・ガマ

	心から歌おう
	マルタ十字は我が旗
	英雄ポルトガル人の名を冠する
	ヴァスコ・ダ・ガマ、あなたの名声はこうして築かれた

	あなたの絶大なファンは大喜び
	ブラジルの南北
	地上に輝く君の星
	海を照らす

	陸上競技では、あなたは腕だ
	ボート競技は不滅だ
	フットボール界では
	ブラジルとポルトガルの結束

	陸上競技は腕だ
	ボート競技では、あなたは不滅です。
	サッカーでは
	ブラジルとポルトガルの団結

	みんなで心を込めて歌おう
	マルタ十字は私の旗！
	英雄ポルトガル人の名を冠する
	ヴァスコ・ダ・ガマ、それが君が有名になった理由だ

	あなたの膨大なファンはとても幸せです
	この国の南北、南北
	地上に輝く君の星
	海を照らす

	陸上競技では、あなたは腕だ
	ボート競技は不滅だ
	フットボール界では、君は不滅だ
	ブラジルとポルトガルの結束

	陸上競技は腕だ
	ボート競技では、あなたは不滅です。
	サッカーでは
	ブラジルとポルトガルの結束
	*/
    return;
}
int main()
{
    while(!is_sorted(v.begin(),v.end()))
    {
        pray();
    }

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

With this quite reliable method, one can hope that the array will be sorted in $$$O(Faith^{-1})$$$ time complexity.

Conclusion

I hope you enjoyed this trip through the bad sorting algorithms. This is merely an introduction and I have yet to see everything bad algorithms have to offer. I find them interesting because the way they manage to get such a bad complexity is quite creative.