Bogo Sorter Algorithm
Bogo Sort, also known as permutation sort, stupid sort, or slow sort, is a highly inefficient sorting algorithm that works by generating random permutations of its input array and checking if the generated permutation is sorted or not. The algorithm is based on the principle of "trial and error" and is more of a whimsical demonstration of the concept rather than being used in practical applications. Bogo Sort is notoriously known for its worst-case performance, where the time complexity is unbounded, which means it can take an incredibly long time to sort even a very small list.
The algorithm begins by checking if the input array is already sorted. If it is, the algorithm terminates. If not, the algorithm randomly shuffles the elements and checks again. This process is repeated until the shuffled array is sorted. Theoretically, the algorithm could run forever since there is no guarantee that a sorted permutation will ever be generated. However, on average, the number of iterations required grows factorially with the size of the input, making Bogo Sort highly impractical for any real-world use. It is mainly used for educational purposes, as a demonstration of an algorithm that should never be used in practice due to its inefficiency.
using System;
using System.Collections.Generic;
namespace Algorithms.Sorters.Comparison
{
/// <summary>
/// Class that implements bogo sort algorithm.
/// </summary>
/// <typeparam name="T">Type of array element.</typeparam>
public class BogoSorter<T> : IComparisonSorter<T>
{
private readonly Random random = new Random();
/// <summary>
/// TODO.
/// </summary>
/// <param name="array">TODO. 2.</param>
/// <param name="comparer">TODO. 3.</param>
public void Sort(T[] array, IComparer<T> comparer)
{
while (!IsSorted(array, comparer))
{
Shuffle(array);
}
}
private bool IsSorted(T[] array, IComparer<T> comparer)
{
for (var i = 0; i < array.Length - 1; i++)
{
if (comparer.Compare(array[i], array[i + 1]) > 0)
{
return false;
}
}
return true;
}
private void Shuffle(T[] array)
{
var taken = new bool[array.Length];
var newArray = new T[array.Length];
for (var i = 0; i < array.Length; i++)
{
int nextPos;
do
{
nextPos = random.Next(0, int.MaxValue) % array.Length;
}
while (taken[nextPos]);
taken[nextPos] = true;
newArray[nextPos] = array[i];
}
for (var i = 0; i < array.Length; i++)
{
array[i] = newArray[i];
}
}
}
}
