Yesterday I was thinking about terrible sorting algorithms, e.g. bogosort, worstsort. One of the issues I have with these is just how well they perform for small data sets. It was troubling me, and upon sleeping last night an epiphany came, which I have documented here (see below for code).
To implement bgesort, perform the following:
Create an array the same size as the data source
Populate the array with random integers, at each index calculating a checksum value vs. the original data source index
If the checksum is valid, check if the array is sorted. If so finish, else go to step 1
This is truly abhorrent for a large search space. The average speed for sorting an array of size 1 is 34.5 seconds. I am quite pleased with these results.
I have no idea what the O notation for this would be; if someone could work it out that would be amazing.
Results
All results average of 5 runs.
Code
class BGESort
{
// "Battle not with monsters, lest ye become a monster, and if you gaze into the abyss, the abyss gazes also into you."
// – Friedrich Nietzsche, Beyond Good and Evil
private Random rand = new Random();
private int searchSpace = int.MaxValue;
public BGESort(int searchSpace = int.MaxValue)
{
this.searchSpace = searchSpace;
}
public int[] Sort(int[] data)
{
while (true)
{
// we will attempt to discover the sorted array
int[] candidate = new int[data.Length];
double checksum1 = 0d;
int checksum2 = 0;
for (int i = 0; i < data.Length; i++)
{
candidate[i] = rand.Next(searchSpace);
// i'm not a mathematician, so I have no idea if this works in all scenarios
// a novel (?) way of comparing two arrays contain the same elements without sorting
checksum1 += Math.Sqrt(data[i]) - Math.Sqrt(candidate[i]);
checksum2 += data[i] - candidate[i];
}
// ignore floating point issues
checksum1 = Math.Round(checksum1, 14);
// if the checksum is zero we have an array of equal elements
if (checksum1 == 0d && checksum2 == 0 && IsSorted(candidate))
{
return candidate;
}
}
}
private bool IsSorted(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (arr[i - 1] > arr[i])
{
return false;
}
}
return true;
}
}