Bogosort: The Stupid Sorting Algorithm

Sorting algorithms are fundamental to computer science and play a crucial role in various applications, such as searching, data mining, and data analysis. In general, sorting algorithms take an unordered list of items and arrange them in a specific order, such as ascending or descending order. There are many sorting algorithms available, each with its own strengths and weaknesses. Some algorithms are highly efficient and can sort large amounts of data in a short time, while others are less efficient and can only be used for small datasets. One algorithm that falls into the latter category is the Bogosort algorithm.

What is Bogosort?

Bogosort is a sorting algorithm that is also known by other names such as permutation sort, stupid sort, slowsort, or bozosort. The algorithm is based on the "generate and test" paradigm and is widely regarded as one of the least efficient sorting algorithms. The idea behind the algorithm is to generate a random permutation of the input list and test if the generated permutation is sorted. If the permutation is not sorted, the algorithm generates another random permutation and tests it again. The algorithm repeats this process until a sorted permutation is found.

The Bogosort algorithm has an average time complexity of O(n*n!) and a worst-case time complexity of O(∞). This means that the algorithm can take an extremely long time to sort even a small list of items. In fact, the algorithm's name is derived from the word "bogus" since the algorithm can produce bogus results or take an indefinite amount of time to produce a correct result.

Implementing Bogosort in Elixir

Let's take a look at how the Bogosort algorithm can be implemented in Elixir. The code below shows an implementation of the Bogosort algorithm in Elixir.

defmodule Bogosort do
  @spec sort(list(any())) :: list(any())
  def sort(list) do
    new_list = Enum.shuffle(list)

    if is_sorted(new_list) do
      new_list
    else
      sort(list)
    end
  end

  defp is_sorted([_element]), do: true
  defp is_sorted([element1, element2 | _]) when element1 > element2, do: false
  defp is_sorted([_element1, element2 | rest]), do: is_sorted([element2 | rest])
end

The Bogosort module contains a single function, sort/1, that takes a list of any data type and returns the sorted list. The function starts by generating a random permutation of the input list using the Enum.shuffle/1 function. The if statement checks if the generated permutation is sorted using the is_sorted/1 helper function. If the permutation is sorted, the function returns the permutation. If the permutation is not sorted, the function calls itself recursively until a sorted permutation is found.

The is_sorted/1 helper function is used to check if a list is sorted. The function uses pattern matching to check if the list contains only one element, in which case the function returns true. If the list contains two or more elements, the function checks if the first two elements are in ascending order. If they are not, the function returns false. If they are in ascending order, the function recursively checks the remaining elements in the list.

Testing Bogosort

Let's test the Bogosort function using some sample input lists.

First test

> Bogosort.sort([1, 2, 3])
[1, 2, 3]

The above code should return [1, 2, 3] since the input list is already sorted.

Second test

> Bogosort.sort([1034, 1145, 1163, 1199])
[1034, 1145, 1163, 1199]

The second test sorts a small list of numbers, and since Bogosort works by shuffling the list and checking if it's sorted, it's not surprising that it can sort this list fairly quickly.

Third test

> random_list =
  for _ <- 1..11 do
    Enum.shuffle(1..10000)
    |> Enum.take(1)
  end
(...)

> Bogosort.sort(random_list)
(...)

The third test generates a list of 11 random numbers between 1 and 10,000, shuffles them, and then applies Bogosort to sort the list. Since Bogosort relies on chance, the algorithm may take much longer to sort this list than it did with the previous example. It's also possible that Bogosort may never sort the list at all, as the algorithm relies on randomly shuffling the list until it happens to be sorted.

Thanks

It's always great to see people sharing their knowledge and insights with others. In this case, a big thank you to Manuel Rubio for mentioning Bogosort in his newsletter. While Bogosort may not be the most efficient sorting algorithm, it's still an interesting and quirky algorithm that can teach us a lot about the fundamentals of computer science. By exploring different sorting algorithms, we can gain a deeper understanding of how computers work and how we can use them to solve problems. So once again, thank you to Manuel Rubio for sharing his knowledge and helping to spread the word about Bogosort.

Acknowledgements

This text was created by ChatGPT and adapted by me based on this notebook