1. 버블정렬

input = [4,6,2,9,1]

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(n - i - 1):      # Q. 여기서ㅓ왜 n - i - 1 일까요?
            if array[j] > array[j + 1]:  # A. array[j] 와 array[j + 1] 을 비교할거라, 마지막 원소까지 가지 않아도 되기 때문이에요!
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

bubble_sort(input)
print(input)



# j => 5 - 0 - 1 : 4
# a[0]: 4 > a[1]: 6
# a[1]: 6 > a[2]: 2     -> [4, 2, 6, 9, 1]
# a[2]: 6 > a[3]: 9
# a[3]: 9 > a[4]: 1     -> [4, 2, 6, 1, 9]

# j => 5 - 1 - 1 : 3
# a[0]: 4 > a[1]: 2     -> [2, 4, 6, 1, 9]
# a[1]: 4 > a[2]: 6
# a[2]: 6 > a[3]: 1     -> [2, 4, 1, 6, 9]

# j => 5 - 2 - 1 : 2
# a[0]: 2 > a[1]: 4
# a[1]: 4 > a[2]: 1     -> [2, 1, 4, 6, 9]

# j => 5 - 3 - 1 : 1
# a[0]: 2 > a[1]: 1     -> [1, 2, 4, 6, 9]

2. 선택정렬

input = [4,6,2,9,1]

def selection_sort(array):
    n = len(array)
    for i in range(n-1):
        min_index = i
        for j in range(n-i):
            if array[i+j] < array[min_index]:
                min_index = i+j

        array[i], array[min_index] = array[min_index], array[i]
    return array

selection_sort(input)
print(input)




# a[0+0] = 4 < a[4] = 1
# a[0+1] = 6 < a[4] = 1
# a[0+2] = 2 < a[4] = 1
# a[0+3] = 9 < a[4] = 1
# a[0+4] = 1 < a[4] = 1    ->  [1,6,2,9,4]

# a[1+0] = 6 < a[4] = 4
# a[1+1] = 2 < a[4] = 4    ->  min_index = 2 -> a[1], [2] = a[2], a[1] -> [1,2,6,9,4]

# a[2+0] = 6 < a[4] = 4
# a[2+1] = 9 < a[4] = 4    ->  [1,2,4,9,6]

# a[3+0] = 9 < a[4] = 6    ->  [1,2,4,6,9]


# [4 6 2 9 1]
#  _       _
# [1 6 2 9 4]
#    _ _
# [1 2 6 9 4]
#      _ _
# [1 2 4 9 6]
#        _ _
# [1 2 4 6 9]

3. 삽입정렬

input = [4, 6, 2, 9, 1]

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):   # 1, 2, 3, 4
        for j in range(i):
            if array[i-j-1] > array[i-j]:
                array[i-j-1], array[i-j] = array[i-j], array[i-j-1]
            else:
                break
    return array

insertion_sort(input)
print(input)


# array[1-0-1]: 4  > array[1-0]: 6

# array[2-0-1]: 6 > array[2-0]: 2 -> [4,2,6,9,1]
# array[2-1-1]: 4 > array[2-1]: 2 -> [2,4,6,9,1]

# array[3-0-1]:6 > array[3-0]: 9
# array[3-1-1]:4 > array[3-1]: 6
# array[3-2-1]:2 > array[3-2]: 4

# array[4-0-1]: 9 > array[4-0]: 1 -> [2,4,6,1,9]
# array[4-1-1]: 6 > array[4-1]: 1 -> [2,4,1,6,9]
# array[4-2-1]: 4 > array[4-2]: 1 -> [2,1,4,6,9]
# array[4-3-1]: 2 > array[4-3]: 1 -> [1,2,4,6,9]


# [4 6 2 9 1]
#    _ _
# [4 2 6 9 1]
#  _ _
# [2 4 6 9 1]

#        _ _
# [2 4 6 1 9]
#      _ _
# [2 4 1 6 9]
#    _ _
# [2 1 4 6 9]
#  _ _
# [1 2 4 6 9]