The Algorithms logo
The Algorithms
关于捐赠

Bogo Sort

p
A
H
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();

    /// <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];
        }
    }
}