Bogo Sort 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.
package Sorts;

import java.util.Random;


/**
 * @author Podshivalov Nikita (https://github.com/nikitap492)
 * @see SortAlgorithm
 */
public class BogoSort implements SortAlgorithm {

    private static final Random random = new Random();


    private static <T extends Comparable<T>> boolean isSorted(T[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (SortUtils.less(array[i + 1], array[i])) return false;
        }
        return true;
    }

    // Randomly shuffles the array
    private static <T> void nextPermutation(T[] array) {
        int length = array.length;

        for (int i = 0; i < array.length; i++) {
            int randomIndex = i + random.nextInt(length - i);
            SortUtils.swap(array, randomIndex, i);
        }
    }

    public <T extends Comparable<T>> T[] sort(T[] array) {
        while (!isSorted(array)) {
            nextPermutation(array);
        }
        return array;
    }

    // Driver Program
    public static void main(String[] args) {
        // Integer Input
        Integer[] integers = {4, 23, 6, 78, 1, 54, 231, 9, 12};

        BogoSort bogoSort = new BogoSort();

        // print a sorted array
        SortUtils.print(bogoSort.sort(integers));

        // String Input
        String[] strings = {"c", "a", "e", "b", "d"};

        SortUtils.print(bogoSort.sort(strings));
    }
}

LANGUAGE:

DARK MODE: