심심풀이 땅콩🥜 : 삽입 정렬(Insertion Sort)

삽입 정렬은 정렬되지 않은 부분에서 값을 추출하여 이미 정렬된 부분의 올바른 위치에 삽입하는 방식이다.

arr = [1,6,9,3,4]
len = 5
[n][arr]
i =  0 /	i =  1 /	i =  2 /	i =  3 /	i =  4 /
j =  0 /	j =  0 /	j =  0 /	j =  0 /	j =  0 /
j =  1 /	j =  1 /	j =  1 /	j =  1 /
j =  2 /	j =  2 /	j =  2 /
j =  3 /	j =  3 /
j =  4 /

def insertion_sort(arr):

    n = len(arr) # 배열의 길이를 저장

    for i in range(1, n): # 배열 길이 5를 기준으로 1에서 5까지의 범위

        #*는 해당 배열의 값

        key = arr[i] # 1,2,9,3,4를 기준으로 key에 값을 저장 (1일 때 *6)

        j = i - 1 # j의 값을 형성

        while j >= 0 and key < arr[j]: #j는 i가 실행되는 값만큼 차감 (i가 1일 때 *6/ j는 0으로 *1)

            # 0 & 6 < 0 => false

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key #i가 1일 때 *6/ j는 0으로 *1/ arr[j + 1]인 arr[1]은 6에서 6이다. 즉, 변화 없음

        print(arr)

   

arr = [1,6,9,3,4]

insertion_sort(arr)

print(arr)

삽입정렬의 삽입 과정에 주의를 해서 봐야한다. 값의 삽입이 어떻게 어디서 이루어지는지 유심히 보자.