bogo_sort.py

"""
    Bogo Sort
    ---------
    A naive sorting that picks two elements at random and swaps them.

    Time Complexity: O(n * n!)

    Space Complexity: O(1) Auxiliary

    Stable: No

    Psuedo code: None

    **WARNING**: This algorithm may never sort the list correctly.
"""

import random


def sort(seq):
    """
    Takes a list of integers and sorts them in ascending order. This sorted
    list is then returned.

    :param seq: A list of integers
    :rtype: A list of sorted integers
    """

    if len(seq) == 1:
        return seq
    random.seed()
    while not is_sorted(seq):
        if len(seq) == 2:
            i = 0
            j = 1
        else:
            i = random.randint(0, len(seq) - 2)
            j = random.randint(i, len(seq) - 1)
        seq[i], seq[j] = seq[j], seq[i]
    return seq


def is_sorted(seq):
    """
    Takes a list of integers and checks if the list is in sorted order.

    :param seq: A list of integers
    :rtype: Boolean
    """
    return all(seq[i - 1] <= seq[i] for i in range(1, len(seq)))