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

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

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

 

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

 

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

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

^ 다른 정렬들이 궁금하다면 ^

 

---

 

출처: [이것이 코딩 테스트다 with python] 22강

 

1. 삽입 정렬(Insertion Sort)

1) 삽입 정렬의 원리

- 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입 하는 정렬

- 적절한 위치에 삽입한다는 의미에서 '삽입 정렬' 이라고 부른다.

장점	단점
- 선택 정렬처럼 동작을 직관적으로 이해하기는 쉽다. - 실행시간 면에서 선택정렬보다 효율적	- 구현 난이도가 높음

- 삽입정렬은 이미 정렬된 영역(검은 Box)과, 아직 정렬되지 않은 영역(검은 box의 오른쪽 숫자들)로 나뉜다. - 정렬은 두 번째 요소부터 자신의 왼쪽(첫 번째 요소)와 비교해 나간다.(한칸 씩 왼쪽으로 이동) - 이후 자신보다 작은 숫자를 발견하면, 그 뒤에 자신을 삽입한다.

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

 

 

 

정말 직관적으로 설명하자면

 

1번 책상에 앉은 학생의 키가 160

2번 책상에 앉은  학생의 키가 180

3번 책상에 앉은  학생의 키가 172

4번 책상에 앉은  학생의 키가 158

5번 책상에 앉은  학생의 키가 177

 

이라고 합시다.

 

🤦‍♀️.oO(얘들아 이렇게 앉으면 4번에 앉은 애는 어떡하니...)

1번 2번 비교: 1번 160 < 2번 180

: 오케이 그대로 앉아

 

2번 3번 비교 : 2번 180 < 3번 172

: 2번에 앉은 얘야... 너가 거기 앉으면 뒤에 앉은 친구들은 칠판을 못 봐요...

[160, 180, 172, 158, 177] >> [160, 172, 180, 158, 177] 이렇게 자리 바꿔

 

3번 4번 비교: 3번 172 < 4번 158

: 4번 너 뭐야? 칠판 못 보잖아... 맨 앞으로 가... 대체 왜 이렇게들 앉은 거니...

[160, 172, 180, 158, 177]  >> [158, 160, 172, 180, 177] 

 

4번 5번 비교: 4번 180 < 5번 177

: 5번 너 뭐야 더 작으면서 왜 거기에 앉았어? 앞으로 가

[158, 160, 172, 180, 177] >> [158, 160, 172, 177, 180]

👥👥👤.oO(잘 보인다 헤헤)

👩‍🏫.oO(만족)

 

이렇게 하는 걸 삽입 정렬이라고 한다.

선택 정렬이 양옆으로만 움직이면서 계속 이리 보내고 저리 보내고 하는 거라면,

삽입 정렬은 양옆에 붙은 값들끼리 비교하면서 앞으로 고정시키다가 더 작은 수가 나타나면 걔를 적절한 위치로 이동시키는 정렬이라고 생각하면 된다.

 

다른 방법으로 다시 설명하자면,

(a)  [A] 는 두 번째 요소(7)부터 시작    :  [A] 는 앞에 있는 숫자와 비교하면서 작은 숫자를 만나면 멈춘다    :  [A] (7)은, 자기보다 작은 숫자(3)를 시작하자마자 만나서 작업 끝 (b) 다음  [A] 인 숫자 '2'는 자기보다 작은 숫자를 못만나서 맨 앞까지 이동 (c) 다음  [A]  숫자 '5'는 자기보다 작은 숫자인 '3'을 만나서 그 뒤에 삽입  (d) 다음  [A]  숫자 '1'은 자기보다 작은 숫자가 없으므로 맨 앞까지 한칸씩 이동 (e) 다음 [A] 숫자 '4'는 자기보다 작은 숫자 '3'을 만나서 그 뒤에 삽입 (f) 마지막 요소인 4까지 [A] 처리 작업 종료 >> 정렬 최종 완성

출처: [위키백과] 삽입 정렬의 예

이렇게 됩니다.

 

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]

삽입 정렬의 코드는 위와 같습니다.

 

뜯어보면 위와 같습니다.

 

 

시간 복잡도가 궁금하다면?

 

 

글 마침