from random import randint

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

def quickSort(aList):
    if len(aList) <= 1:
        return aList
    return quickSort([i for i in aList[1:] if i < aList[0]]) + [aList[0]] + quickSort([i for i in aList[1:] if i >= aList[0]])

def selectSort(aList):
    length = len(aList)
    for i in range(length-1):
        idx = i
        for j in range(i+1, length):
            if aList[idx] > aList[j]:
                idx = j
        if idx != i:
            aList[i], aList[idx] = aList[idx], aList[i]
    return aList

def insertSort(aList):
    length = len(aList)

    for i in range(1, length):
        for j in range(i-1, -1, -1):
            if aList[i] < aList[j]:
                aList[i], aList[j] = aList[j], aList[i]
                i = j
    
    return aList

def shellSort(aList):
    length = len(aList)
    step = length // 2

    while step > 0:
        for i in range(step, length):  
            while i >= step and aList[i-step] > aList[i]:
                aList[i-step] , aList[i] = aList[i], aList[i-step]
                i -= step
            
        step //= 2
    
    return aList

def mergeSort(left, right):
    result = []
    left_idx = right_idx = 0
    left_len, right_len = len(left), len(right)

    while left_idx < left_len and right_idx < right_len:
        if left[left_idx] < right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1
    
    while left_idx < left_len:
        result.append(left[left_idx])
        left_idx += 1
    
    while right_idx < right_len:
        result.append(right[right_idx])
        right_idx += 1
    
    return result

def merge(aList):
    mid = len(aList) // 2

    if len(aList) <= 1:
        return aList
    
    return mergeSort(merge(aList[:mid]), merge(aList[mid:]))

def heapSink(aList, length, parent):
    child_idx = 2 * parent + 1

    while child_idx < length:
        if child_idx + 1 < length and aList[child_idx] < aList[child_idx+1]:
            child_idx = child_idx + 1
        
        if aList[parent] < aList[child_idx]:
            aList[parent], aList[child_idx] = aList[child_idx], aList[parent]
            heapSink(aList, length, child_idx)
        else:
            break

def heapSort(aList):
    length = len(aList)
    for i in range(length//2, -1, -1):
        heapSink(aList, length, i)
    
    for i in range(length-1, 0, -1):
        aList[0], aList[i] = aList[i], aList[0]
        heapSink(aList, i, 0)
    
    return aList

def countingSort(aList):
    sorted_list = [0] * (max(aList) + 1)
    for i in aList:
        sorted_list[i] += 1
    
    temp = []
    for i, j in enumerate(sorted_list):
        while j > 0:
            temp.append(i)
            j -= 1
    return temp

def bucketSort(aList, bucketSize=10):
    maxNum = max(aList)
    bucketList = [ [] for i in range(bucketSize+1) ]
    for i in aList:
        bucketList[i//bucketSize].append(i)
    
    aList = []
    for i in bucketList:
        if i:
            aList.extend(insertSort(i))
    
    return aList

def radixSort(aList):
    for i in range(len(str(max(aList)))):
        tmpList = [ [] for i in range(10) ]
        
        for j in aList:
            tmpList[(j//10**i)%10].append(j)
        aList = []
        for k in tmpList:
            if k:
                aList.extend(k)
    return aList


if __name__ == '__main__':
    methods = [bubbleSort, quickSort, selectSort, insertSort, shellSort, heapSort, merge, countingSort, bucketSort, radixSort]

    for fn in methods:
        alist = [ randint(1, 100) for i in range(10) ]
        print('*' * 10 + str(fn) + '*' * 10)
        print(alist)
        print(fn(alist))
        print('*' * 20)