# 01. 삽입 정렬이 무엇인지 찾아보고 구현해보세요
from random import choice

raw_list = list(range(0, 100+1))
target = []
for _ in range(100):
  target.append(choice(raw_list))

print(target)

def ins_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

ins_sort(target)
print(target)

# 02. 퀵 정렬이 무엇인지 찾아보고 구현해보세요.
from random import choice

raw = list(range(0, 100+1))

target = []
for _ in range(100):
    target.append(choice(raw))

print(target)

def quick_sort_sub(a, start, end):
    if end-start <= 0:
        return
    pivot = a[end]
    i = start
    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[end] = a[end], a[i]
    quick_sort_sub(a, start, i - 1)
    quick_sort_sub(a, i + 1, end)

def quick_sort(a):
    quick_sort_sub(a, 0, len(a)-1)

quick_sort(target)
print(target)

# 03. fibonacci  향상

# 04. Memorization -  1
def cal(n):
    i = 1
    if n == 1:
        return i
    i += 1
    if n % 2 == 0:
        return cal(n / 2)
    else:
        return cal((n * 3) + 1)

def sol(n):
    result = []
    for i in range(1, n+1):
        result.append(cal(i))
    return result

print(sol(2))
print(sol(6))
 # 오류 발생 중...(수정 예정 입니다.)