recursive_dropsort.py

#!/usr/bin/env python

import sys
import math
from random import shuffle
import numpy as np

loop_iters = 0
"""
NOTE: I'm pretty sure we're using the word bogo without knowing what it means...
Hence truebogo_sort
"""
def main(size):
    global loop_iters
    loop_iters = 0
    numbers = []
    for i in xrange(size):
        numbers.append(int(np.random.uniform(0, 100)))
        #numbers.append(int(np.random.normal(10, 4)))
        #numbers.append(int(np.random.poisson(10)))
        #numbers.append(int(np.random.logistic(10, 10)))

    save = [x for x in numbers]
    sorted_numbers = bogo_sort(numbers)
    print "bogo: %d iterations for %d elements" % (loop_iters, size)

    loop_iters = 0
    if size > 5:
        print "true bogo: disabled for large inputs"
    else:
        truebogo_sort(numbers)
        print "true bogo: %d iterations for %d elements" % (loop_iters, size)

    loop_iters = 0
    bogo_sort(numbers, True)
    print "bjorge bogo (lol): %d iterations for %d elements" % (loop_iters, size)

    loop_iters = 0
    insertion_sort(numbers)
    print "insertion: %d iterations for %d elements" % (loop_iters, size)

    loop_iters = 0
    merge_sort(numbers)
    print "merge: %d iterations for %d elements" % (loop_iters, size)

 
def truebogo_sort(x):
    global loop_iters
    def inorder(x):
        i = 0
        j = len(x)
        while i + 1 < j:
            if x[i] > x[i + 1]:
                return False
            i += 1
        return True

    while not inorder(x):
        loop_iters += 1
        # Assuming the shuffle step is O(1) which it obviously isn't
        shuffle(x)
    return x

def insertion_sort(l):
    global loop_iters
    for i in xrange(1, len(l)):
        loop_iters += 1
        j = i-1 
        key = l[i]
        while (l[j] > key) and (j >= 0):
           loop_iters += 1
           l[j+1] = l[j]
           j -= 1
        l[j+1] = key

def bogo_sort(unsorted_numbers, bjorgeSort=False):
    global loop_iters
    if len(unsorted_numbers) <= 1:
        return unsorted_numbers

    last = unsorted_numbers[0]
    drop_list = []
    sorted_list = []

    if bjorgeSort:
        """
        Alternatively, the following loop can be looked at as a way to pick merge sort's pivot point
        where the pivot point is chosen based on the first non-sorted element.
        """
        for idx, i in enumerate(unsorted_numbers):
            loop_iters += 1
            if last > i:
                # I don't need to count iterations here because I'm not looking any further into the list
                drop_list = unsorted_numbers[idx:]
                break
            else:
                sorted_list.append(i)
                last = i
    else:
        """
        Alternatively, the following loop can be looked at as a way to pick merge sort's pivot point
        where the pivot point is chosen based on the first non-sorted element. Finally, the remaining elements
        are looked at and elements that don't disrupt the sorting to the left of our pivot point are moved into
        position.

        Recurse on [1,2,3,2,1,5,6,3,2]
            Recurse on [2,1,5,6,3,2]
                Recurse on [1,5,6,3,2]
                    Recurse on [3,2]
                    return merge([3], [2])
                return merge([1,5,6], [2,3])
            return merge([2], [1,2,3,5,6])
        return = merge([1,2,3], [1,2,2,3,5,6])
        """
        for i in unsorted_numbers:
            loop_iters += 1
            if last > i:
                drop_list.append(i)
            else:
                sorted_list.append(i)
                last = i

    sorted_drop_list = bogo_sort(drop_list, bjorgeSort)
    return merge(sorted_list, sorted_drop_list)

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    middle = int( len(lst) / 2 )
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

def merge(left, right):
    global loop_iters
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        loop_iters += 1
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    if j == len(right):
        result = result + left[i:]

    if i == len(left):
        result = result + right[j:]

    return result



if __name__ == "__main__":
    size = 100
    if len(sys.argv) > 1:
        size = int(sys.argv[1])
    main(size)