삽입 정렬

☝ 삽입 정렬이란 가장 작은 수를 맨 앞으로 보내주는 (삽입하는) 정렬이다.

🎫 개념

배열을 순회하며 해당 인덱스의 값이 정렬 시 위치해야 하는 인덱스에 값을 삽입하는 것이다.

❓ 예시

예를 들어 [35, 47, 84, 15, 17, 22, 29] 이라는 배열 arr이 있다고 하자.

✔ step1
[35, 47, 84, 15, 17, 22, 29]
35, 47, 84는 84까지 순회했을 경우엔 각자 제자리에 있는 것이므로 변동이 없고, 15는 84, 47, 35를 거쳐 대소 비교를 통해
[15, 35, 47, 84, 17, 22, 29]

✔ step2
[15, 35, 47, 84, 17, 22, 29]
17은 84, 47, 35를 거쳐
[15, 17, 35, 47, 84, 22, 29]

✔ step3
[15, 17, 35, 47, 84, 22, 29]
22는 84, 47, 35를 거쳐
[15, 17, 22, 35, 47, 84, 29]

✔ step4
[15, 17, 22, 35, 47, 84, 29]
47, 84는 변동 x
29가 84, 47, 35를 거쳐
[15, 17, 22, 29, 35, 47, 84]

💻 삽입 정렬 코드 구현 (python)

def insert_sort(arr, N):
    for i in range(N-1):
        for j in range(i+1, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
    return arr
if __name__ == '__main__':
    arr = []
    N = int(input())

    for _ in range(N):
        arr.append(int(input()))

    arr = insert_sort(arr, N)

    for i in arr:
        print(i)

⏰ 시간 복잡도 및 Big O 표기

2중 for문이 N에 달려있으므로 N(N+1)/2를 Big O 표기법으로 표현하면 O(N^2)이다.
만약 이미 정렬이 되어있다면 O(N)이다.