__author__ = 'tanza'

import random, time
import numpy as np






def mergeSortTry(part):
    """takes an unsorted list and returns a sorted list
    """

    try:
        part[1]
        mid = len(part)/2
        left = mergeSortTry(part[:mid])
        right = mergeSortTry(part[mid:])

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] > right[j]:
                part[k] = right[j]
                j += 1
            else:
                part[k] = left[i]
                i += 1
            k += 1

        if i < j:
            remaining = left
            r = i
        else:
            remaining = right
            r = j

        while r < len(remaining):
            part[k] = remaining[r]
            r += 1
            k += 1

        return part
    except:
        return part


def mergeSortLen(part):
    """takes an unsorted list and returns a sorted list
    """

    if len(part) > 1:
        mid = len(part)/2
        left = mergeSortLen(part[:mid])
        right = mergeSortLen(part[mid:])

        i = 0
        j = 0
        k = 0

        llen = len(left)
        rlen = len(right)
        while i < llen and j < rlen:
            if left[i] > right[j]:
                part[k] = right[j]
                j += 1
            else:
                part[k] = left[i]
                i += 1
            k += 1

        if i < j:
            remaining = left
            remlen = llen
            r = i
        else:
            remaining = right
            remlen = rlen
            r = j

        while r < remlen:
            part[k] = remaining[r]
            r += 1
            k += 1

        return part
    else:
        return part


def timsort(arr):
    arr.sort()


def insertionSort(arr):
    for i in np.arange(1, len(arr)):
        currentvalue = arr[i]
        position = i
        while position > 0 and arr[position-1] > currentvalue:
            arr[position] = arr[position-1]
            position = position-1
        arr[position] = currentvalue


def quicksort(arr):
    quicksorthelper(arr, 0, len(arr)-1)

def quicksorthelper(arr, first, last):
    if first < last:
        pivot = partition(arr, first, last)
        quicksorthelper(arr, first, pivot-1)
        quicksorthelper(arr, pivot+1, last)

def partition(arr, first, last) :
    pivot = last
    swap(arr, pivot, last)
    for i in np.arange(first, last):
        if arr[i] <= arr[last]:
            swap(arr, i, first)
            first += 1
    swap(arr, first, last)
    return first

def swap(A, x, y):
  A[x],A[y]=A[y],A[x]


def bubbleSort(arr):
    larr = len(arr)
    for i in np.arange(larr):
        for j in np.arange(larr - i - 1):
            if arr[j] > arr[j+1]:
                temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp

def genRandomList(n = 21, neatness = 0.50, sparsity=20):
    return list(np.random.randint(low=-n*sparsity, high=n*sparsity, size=n))

def genMostlySortedList(n = 21, neatness = 0.50, sparsity=20):
    arr = list(np.random.randint(low=-n*sparsity, high=n*sparsity, size=n))
    arr.sort()
    f = 0.05
    larr = len(arr)
    for i in range(int(f * larr) + 1):
        x = random.randint(0, larr-1)
        y = random.randint(0, larr-1)
        temp = arr[x]
        arr[x] = arr[y]
        arr[y] = temp
    return arr

def verify_correct(arr):
    for item,next in zip(arr[:-1], arr[1:]):
        if item <= next:
            continue
        else:
            return False
    return True


def benchmark(method):

    for n in [10, 100]:#, 1000, 10000]:
        best_runtime = None
        correctness = True
        for repeat in range(5):
            x = genRandomList(n=n)
            time_of_start = time.time()
            method(x)
            time_of_end = time.time()
            if best_runtime is None:
                best_runtime = time_of_end - time_of_start
            else:
                best_runtime = min(best_runtime, time_of_end - time_of_start)
            correctness = correctness and verify_correct(x)
        print "{:<20s}".format(str(method.__name__)) + ", " + "mostly sorted=False" + ", " + "{:<8s}".format(str(n)) + ", " + str("%.5f" % (best_runtime)) + ", " + str("correct" if correctness else "incorrect")

        best_runtime = None
        correctness = True
        for repeat in range(5):
            x = genMostlySortedList(n=n)
            time_of_start = time.time()
            method(x)
            time_of_end = time.time()
            if best_runtime is None:
                best_runtime = time_of_end - time_of_start
            else:
                best_runtime = min(best_runtime, time_of_end - time_of_start)
            correctness = correctness and verify_correct(x)
        print "{:<20s}".format(str(method.__name__)) + ", " + "mostly sorted=True " + ", " + "{:<8s}".format(str(n)) + ", " + str("%.5f" % (best_runtime)) + ", " + str("correct" if correctness else "incorrect")

    print "-----------------------------------------------------------"


benchmark(mergeSortLen)
benchmark(timsort)
benchmark(quicksort)
benchmark(insertionSort)
benchmark(bubbleSort)