Exotic Algorithms

Exotic, stupid, funny algorithms

• BogoBogoSort
• BogoSort
• BozoSort
• CommunismSort
• MiracleSort
• StalinSort
• SlowSort

Getting Started

Run each file or import them into your projects

Prerequisites

• python 3 - the programming language used

To run run.py:

• numpy
• pick

To run runplot.py:

• numpy
• matplotlib
• pick

Install all the required packages

pip3 install -r requirements.txt

You may also need to install tkinter

sudo apt-get install python3-tk

Running the tests

Run the files with:

python3 file.py

or put the file in your project folder and import it

import file

Algorithms

BogoBogoSort

• Best Case: O(n)
• Average Case: O(n * (n!)n)
• Worst Case: ∞

def is_sorted(lst):
	cpy = lst[:]
	std = bogoBogoSort(cpy[:-1])
	while cpy[-1] < max(std):
		random.shuffle(cpy)
		std = bogoBogoSort(cpy[:-1])
	return std == lst[:-1]

def bogoBogoSort(lst):
	if len(lst) == 1:
		return lst
	while not is_sorted(lst):
		random.shuffle(lst)
	return lst

BogoSort

• Best Case: O(n)
• Average Case: O(n!)
• Worst Case: ∞

def bogoSort(lst):
    while not is_sorted(lst):
        random.shuffle(lst)
    return lst

BozoSort

• Best Case: O(n)
• Average Case: O(n!)
• Worst Case: ∞

def bozoSort(lst):
    while not is_sorted(lst):
        i, j = int(len(lst)*random.random()), int(len(lst)*random.random())
        lst[i], lst[j] = lst[j], lst[i]
    return lst

CommunismSort

• Best Case: O(n)
• Average Case: O(n)
• Worst Case: O(n)

def communismSort(lst):
    avg = sum(lst) / len(lst) 
    for i in range(len(lst)):
        lst[i] = avg
    return lst

MiracleSort

• Best Case: O(n)
• Average Case: ∞
• Worst Case: ∞

def miracleSort(lst):
    if(is_sorted(lst)):
        return lst
    else:
        miracleSort(lst)

StalinSort

• Best Case: O(n)
• Average Case: O(n)
• Worst Case: O(n)

def stalinSort(lst):
    sorted_list = [lst[0]]
    for i in lst[1:]:
        if i >= sorted_list[-1]:
            sorted_list.append(i)
    return sorted_list

SlowSort

• Best Case: O(n ^ (lg n))
• Average Case: O(n ^ (lg n))
• Worst Case: O(n ^ (lg n))

def slowSort(A, i, j):
    if i >= j:
        return
    m = (i+j)//2
    slowSort(A, i, m)
    slowSort(A, m+1, j)
    if A[m] > A[j]:
        A[m],A[j] = A[j],A[m]
    slowSort(A, i, j-1)