[이코테_코딩테스트] 정렬 알고리즘 - 삽입 정렬 (Insertion Sort)

date

Jul 26, 2023

slug

coding-test-insertion-sort

author

status

Public

tags

Python

코딩테스트

summary

삽입 정렬을 알아보자

type

Post

thumbnail

category

💻코딩테스트

updatedAt

Jul 26, 2023 07:23 AM

삽입 정렬 (Insertion Sort)

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

• 선택 정렬에 비해 구현 난이도는 높지만, 일반적으로 더 효율적으로 동작한다.

삽입 정렬 동작 예시

[Step 0] 첫 번째 데이터 ‘7’은 그 자체로 정렬이 되어 있다고 판단, 두 번째 데이터인 ‘5’가 어떤 위치로 들어갈지 판단한다.

• 이때 ‘7’의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재

[Step 1] 이어서 ‘9’가 어떤 위치로 들어갈지 판단

[Step 2] ‘0’이 어떤 위치로 들어갈지 판단

[Step N] 위 과정을 반복하면 다음과 같이 정렬이 완료된다.

삽입 정렬 소스코드 (Python)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # i부터 1까지 1씩 감소하며 반복
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동 & 작으면 교환
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자신보다 작거나 같은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용

• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
• 최선의 경우 의 시간 복잡도를 가진다.
이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까?

• ‘1’부터 각 원소가 들어갈 위치를 찾기 위해 선형 탐색을 하는데, 자신의 왼쪽 데이터와 비교했을 때 바로 멈추므로 이 된다.

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘” 영상을 보고 작성하였습니다.