[알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python

2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python

[알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python

이전 글에서는 선택정렬(Selection Sort)에 대해서 알아보았습니다. 선택정렬은 가장 원시적인 방법으로 복잡도가 O(N²)에 해당하여 데이터가 늘어날수록 느려지는 단점이 있었습니다.

이번 글에서는 선택정렬처럼 직관적으로 이해하기 쉬우면서 좀 더 효율적인 알고리즘인 삽입정렬에 대해서 알아보도록 하겠습니다. 

 

1. 삽입 정렬(Insertion Sort)

1.1 삽입 정렬의 원리

- 삽입정렬은 요약하자면 '데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입 하는 방법' 입니다. 적절한 위치에 삽입한다는 의미에서 '삽입 정렬(Insertion Sort)'이라고 부릅니다.

- 선택정렬처럼 동작을 직관적으로 이해하기 쉽지만, 선택정렬보다는 구현 난이도가 높고 실행시간 면에서 더 효율적입니다.

 

<그림으로 설명하는 삽입정렬1>

[나무위키] 정렬 알고리즘

1) 삽입정렬은 이미 정렬된 영역(검은 Box)과, 아직 정렬되지 않은 영역(그 오른쪽 숫자들)로 나뉩니다.

2) 정렬은 두번째 요소부터 자신의 왼쪽(첫번째 요소)와 비교해 나가며(한칸 씩 왼쪽으로 이동), 자신보다 작은 숫자를 찾는 순간 그 뒤에 자신을 삽입합니다.

 

 

 

<그림으로 설명하는 삽입정렬 2>

[위키백과] 삽입정렬

 

(a) New_Face는 두번째 요소('7)부터 시작한다. 

   : New_Face는 앞에 있는 숫자와 비교하면서 작은 숫자를 만나면 멈춘다

   : New_Face(7)은, 자기보다 작은 숫자(3)를 시작하자마자 만나서 작업끝

 

(b) 다음 New_Face인 숫자 '2'는 자기보다 작은 숫자를 못만나서 맨앞까지 이동

 

(c) 다음 New_Face 숫자 '5'는 자기보다 작은 숫자인 '3'을 만나서 그 뒤에 삽입 

 

(d) 다음 New_Face 숫자 '1'은 자기보다 작은 숫자가 없으므로 맨앞까지 한칸씩 이동

 

(d) 다음 New_Face 숫자 '4'는 자기보다 작은 숫자 '3'을 만나서 그 뒤에 삽입

 

(f) 마지막 요소인 4까지 New_Face 처리 작업 종료했으므로, 정렬 최종 완성

 

 

1.2 삽입 정렬 파이썬 코드

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): 
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
            
print(array)
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

1.3 시간복잡도 

- 삽입정렬의 시간복잡도는 O(N²)로, 앞 글에서 배운 선택정렬과 비슷한 시간이 소요된다. 

- 하지만, 삽입정렬은 데이터가 정렬이 되어있는 경우 매우 빠르게 동작하며, 가장 빠른 경우 O(N)의 복잡도를 가진다.

- 이어서 배울 퀵 정렬 알고리즘과 비교했을 때에도, 일반적으로 퀵정렬이 효율적이나 데이터가 정렬되어있을 경우 삽입정렬이 더 효율적이다. 

 

- 다음 글에서는 퀵 정렬(Quick Sort)에 대해서 알아보도록 하겠습니다. 

2021.07.11 - [알고리즘(Algorithm)] - [알고리즘][정렬] ③ 퀵 정렬 (Quick Sort) - Python

[알고리즘][정렬] ③ 퀵 정렬 (Quick Sort) - Python

 

<참고> '이것이 코딩 테스트다 with 파이썬'

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고