'''
# Create by LokiSharp(loki.sharp#gmail) at 2017-1-22
'''

TOTAL = 5000


def sortTest(func, total=1000):
    import random, copy, operator, math, time
    arrList = [i for i in range(-math.floor(total / 2), math.ceil(total / 2))]
    arrListR = copy.deepcopy(arrList)
    while operator.eq(arrList, arrListR):
        random.shuffle(arrListR)
    # print("--- [Origin List]", arrList, "Use", func.__name__,"with Total:", len(arrList))
    # print("--> [Random List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
    start = time.clock()
    arrListR = func(arrListR)
    end = time.clock()
    runtime = end - start
    # print("--> [Sorted List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
    if operator.eq(arrList, arrListR):
        print("[Success]", func.__name__, "with Total:", len(arrList), "in %.5fs" % runtime)
        return True
    else:
        print("[Fail]", func.__name__, "with Total:", len(arrList), "in %.5fs" % runtime)
        return False


def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i  i 
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr


def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i - 1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex + 1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
    return arr


def shellSort(arr):
    import math
    gap = 1
    while (gap < len(arr) / 3):
        gap = gap * 3 + 1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = temp
        gap = math.floor(gap / 3)
    return arr


def mergeSort(arr):
    import math
    if (len(arr) < 2):
        return arr
    middle = math.floor(len(arr) / 2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))


def merge(left, right):
    result = []
    while left and right:
        if left[0]  arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)


def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]


def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr) - 1, 0, -1):
        swap(arr, 0, i)
        arrLen -= 1
        heapify(arr, 0)
    return arr


def countingSort(arr, maxValue=None):
    bucketLen = maxValue + 1
    bucket = [0] * bucketLen
    sortedIndex = 0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]] = 0
        bucket[arr[i]] += 1
    for j in range(bucketLen):
        while bucket[j] > 0:
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
    return arr

def radix_count(exp1):
    global list
    n = len(list)
    output = [0] * (n)
    count = [0] * (10)
    for i in range(0, n):
        index = (list[i] / exp1)
        count[(index) % 10] += 1
    for i in range(1,10):
        count[i] += count[i - 1]
    i = n - 1
    while i >= 0:
        index = (list[i]/exp1)
        output[count[(index) % 10] - 1] = list[i]
        count[(index) % 10] -= 1
        i -= 1
    i = 0
    for i in range(0,len(list)):
        list[i] = output[i]

def radixSort():
    global list
    max1 = max(list)
    exp = 1
    while max1 / exp > 0:
        radix_count(exp)
        exp *= 10


if __name__ == '__main__':
    sortTest(bubbleSort, TOTAL)
    sortTest(selectionSort, TOTAL)
    sortTest(insertionSort, TOTAL)
    sortTest(shellSort, TOTAL)
    sortTest(mergeSort, TOTAL)
    sortTest(quickSort, TOTAL)
    sortTest(heapSort, TOTAL)
    sortTest(radixSort, TOTAL)