tuvo1106

def shell(l:list):
    arr = l[::]
    n = 0
    while (n < len(arr) // 3):
        n = n * 3 + 1
    while (n > 0):
        for i in range(int(n), len(arr)):
            tmp = arr[i]
            j = i
            while j >= n and arr[j - n] > tmp:

tuvo1106

def shaker(l:list):
    arr = l[::]
    sort = True
    start = 0
    end = len(arr)
    while (sort):
        sort = False
        for i in range(start, end):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i-1], arr[i]

tuvo1106

def get_digit(num, i):
    """Return the (i)th index of num"""
    return (num // 10**i) % 10

def max_digits(arr):
    """Return the length of the longest element in array"""
    return len(str(max(arr)))

def radix_sort(l:list):
    """Sort an array of positive integers"""

tuvo1106

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:

tuvo1106

def countsort(l:list):
    arr = l[::]
    k = 0
    new_list = (max(arr) + 1) * [0]
    for j in arr:
        new_list[j] += 1
    for i in range(max(arr) + 1):
        if i != 0:
            new_list[i] += new_list[i - 1]
        while new_list[i] != k:

tuvo1106

def merge_sort(l:list):
    arr = l[::]
    if len(arr) < 2:
        return arr
    mid = len(arr)//2;
    left = arr[:mid]
    right = arr[mid:]
    return merge(merge_sort(left), merge_sort(right))

def merge(l, r):

tuvo1106

def quicksort(l:list):
    arr = l[::]
    if len(arr) <= 1:
        return arr
    l = [x for x in arr[1:] if x <= arr[0]]
    r = [x for x in arr[1:] if x > arr[0]]
    return quicksort(l) + arr[0:1] + quicksort(r)

tuvo1106

def quicksort(l:list) -> list:
    arr = l[::]
    if len(arr) <= 1:
        return arr
    l = [x for x in arr[1:] if x <= arr[0]]
    r = [x for x in arr[1:] if x > arr[0]]
    return quicksort(l) + arr[0:1] + quicksort(r)

tuvo1106

def selection(l: list):
    arr = l[::]
    for i in range(len(arr)):
        m = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[m]:
                m = j
        if i != m:
            arr[i], arr[m] = arr[m], arr[i]
    return arr

tuvo1106

def insertion(l: list):
    arr = l[::]
    for i in range(len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
    return arr