이 글은 나동빈님의 "이것이 코딩테스트다 with 파이썬"책과 유튜브 강의를
교재로 삼아 공부한 후 나의 이해한 내용을 정리한 글입니다

삽입 정렬

핵심 아이디어

정렬이 필요한 요소를 필요한 위치로 자리를 "이동" 시킨다 (삽입 한다)

정렬 진행 방식

1 ) 정렬할 배열을 탐색하여 요소를 확인하고 그 요소의 왼쪽과의 대소를 비교한다.
2 ) 만약 왼쪽의 요소보다 현재 요소가 작다면 자리를 바꿔준다.
3 ) 왼쪽의 요소가 현재 요소보다 더 작을 때까지 2 )의 과정을 시행한다.
4 ) 3 )의 과정이 완료 되었다면 정렬을 시행할 다음 요소로 넘어간다.
5 ) 주어진 배열을 모두 탐색할 때까지 2) 3) 4)의 과정을 반복하여 시행한다.
6 ) 정렬 완료

• 삽입 정렬의 설명을 보면 "적절한 위치에 삽입한다"라는 구문이 있다.
  이 "삽입"이라는 단어가 처음에는 너무 애매하고 확 와닿지가 않았다.
  사실 앞에서 공부한 선택, 버블정렬의 경우도 자리를 바꾸는 과정을 거치는 정렬이라 자리를 바꾸는 것과 삽입한다는 것이 헷갈렸었기 때문이다.
  특히 버블정렬은 오른쪽과 대소를 비교하면서 자리를 바꾸는데 처음에는 대체 무슨 차이일까 하는 생각을 했었다.

• 그래서 내 나름대로 이해한 방법은 "적절한/필요한 위치로 이동 시킨다"라고 생각하고 코드를 보니 조금 더 와닿았던것 같다.

• 사실상 현재 요소의 왼쪽을 보면서 대소를 비교하여 현재 요소가 크면 왼쪽으로 이동하고 작으면 스탑하고 다음 요소로 넘어가기 때문에 이동이라는 단어가 더 이해하기 편했던 것 같다.

가장 큰 차이점은 현재 요소의 왼쪽에 있는 요소들은 이미 정렬이 되어 있다고 가정하기 때문에 조건을 만족하는 요소를 만나는 순간 적절한 위치에 삽입 되었다고 가정하고 다음 요소 탐색으로 넘어간다.

• 또한 정렬 되었다고 가정하는 요소와 현재 요소를 비교 한다는 차이점 또한 존재한다.

기본 코드 구조

def f_insertion(arr):
    for i in range(len(arr)):
        j = i
        while j > 0 and arr[j] < arr[j - 1]:
            temp = arr[j]
            arr[j] = arr[j - 1]
            arr[j - 1] = temp
            j -= 1
    return arr

코드 설명

삽입 정렬은 현재 탐색하고 있는 요소를 왼쪽의 값과 비교하여 현재 요소가 비교하는 값보다 더 클때까지 계속해서 이동시키는 방식의 알고리즘이다.

코드 1

def f_insertion(arr):
    for i in range(len(arr)):
        j = i

다른 정렬 알고리즘과 마찬가지로 정렬할 배열을 탐색해야 하기 때문에 for문을 이용한다.
여기서 for문안에 삽입된 j = i라는 변수 선언/할당문을 보자.
i는 정렬이 필요한 배열 안 현재 탐색하는 요소의 인덱스이다.
위에서 말했듯이 이 i를 계속해서 -1해가며 (왼쪽의 인덱스와 비교하여 이동시킬 때) 이동시켜야 한다.
그런데 이 i 값을 계속해서 바꿀 순 없으므로 j 라는 변수를 새로 선언하여 i 를 할당시켜 사용 할 것이다.

코드 2

while j > 0 and arr[j] < arr[j - 1]:
   temp = arr[j]
   arr[j] = arr[j - 1]
   arr[j - 1] = temp
   j -= 1

위에서 새롭게 선언하여 할당한 j 는 계속하여 -1을 시행하여 (왼쪽의 값과 비교하여 더 작다면) 자리를 바꿔줘야 한다.
따라서 j의 값이 더 크다면 반복문을 멈추고 다음 j를 시행하야 하기 때문에 for문이 아닌 while문을 사용 하였다.

while문의 탈출 조건을 보자
j 가 0일때는 왼쪽의 값이 아예 없으므로 시행할 필요가 없으므로 j > 0의 조건을, 대소 비교 조건도 같이 탈출 조건에 넣어서 설정한다.

위의 while문을 탈출하면 다음 i을 새롭게 탐색한다.
즉 while문을 탈출한다는 것은 왼쪽의 요소가 정렬이 되었다는 것이다.
삽입 정렬의 핵심은 여기에 있다.

i 를 왼쪽의 값들과 비교하여 이동시킨다는 것은 현재 i 의 왼쪽은 정렬이 되어 있다는 것을 가정한다는 것이고, 실제로 while문을 통하여 정렬이 완료 되어 있는 상태이다

따라서 위 과정을 for문이 종료 될 때 까지 반복하면 최종적으로 삽입 정렬이 완료된다.

최종 코드 // 입 출력

arr = [10, 17, 0, 0, 3, 6, 18, 2]

def f_insertion(arr):
    for i in range(len(arr)):
        j = i
        while j > 0 and arr[j] < arr[j - 1]:
            temp = arr[j]
            arr[j] = arr[j - 1]
            arr[j - 1] = temp
            j -= 1
    return arr

print(f_insertion(arr))

==> [0, 0, 2, 3, 6, 10, 17, 18]

처음에 삽입 정렬을 공부할때 위에 말했던 "삽입한다"라는 단어 때문에 많이 헷갈렸었다.
직접 손으로 과정을 써보기도하고, 여러가지 유튜브 영상과 블로그 글을 찾아보며 나만의 방식으로 이해하고 나니 훨씬 수월하게, 확실히 이해하게 된 것 같다.