삽입 정렬(Insertion Sort)이 뭔가요? 버블 정렬과의 차이점

안녕하세요~ 

 

화창한 주일 잘들 보내셨나요? 이제 조금 있으면 개콘이 할 시간이군요. 

 

개콘이 할 시간이라는 건 내일이 월요일이라는 슬픈 사실을 내포하고 있죠 ㅜㅜ

 

그래도 우리는 꾸준히 배워야 합니다. 그래야 남들보다 더 나은 삶을 살 수 있을테니까요 ㅋㅋ

 

자, 이번엔 삽입 정렬에 대해서 포스팅을 하려 합니다. 

 

삽입 정렬이란 이름을 보면 뭔가를 삽입하면서 정렬을 한다라고 추측을 해볼 수 있을 것 같아요. 그쵸? 네, 바로 그 개념을 이용한것이 삽입 정렬입니다.

 

삽입 정렬은 데이터 셋을 두개로 나누어 생각합니다. 하나는 정렬된 셋이고 하나는 정렬되지 않은 셋입니다. 

 

정렬된 셋은 항상 좌측에 위치하게되고 우측에는 앞으로 정렬해야 할 (정렬되지 않은) 남은 데이터 셋이 있습니다. 

 

어떤 요소가 정렬이 되려면 정렬된 데이터 셋에 삽입한다고 해서 붙여진 이름이 바로 삽입 정렬입니다.

 

이렇게 말하면 무슨 말인가 싶죠?

 

이번에도 역시 예제를 통해서 한번 살펴보도록 하겠습니다.

 

아래는 정렬되지 않은 데이터 셋입니다.

 

1단계 : 삽입 정렬의 첫 단계는 버블 정렬처럼 처음 두 개의 데이터를 비교를 합니다. 

 

14와 33을 비교했는데 14가 더 작으니 14를 정렬된 셋 리스트에 삽입합니다. 

 

말이 삽입이지 그냥 그 위치에 넣어두고 개념적으로만 삽입한다고 이해하시면 됩니다.

 

2단계 : 이제 두 번째 요소와 세 번째 요소를 비교합니다. 

 

그랬더니 33이 더 크네요.

 

두 요소의 위치를 바꿉니다. 그리고 27을 14와 또 비교합니다. 14와 27은 정렬되어 있으니 ( 큰 수가 오른쪽에 있으니 ) 그대로 이번 단계는 끝납니다.

 

3단계 : 이제 3번째 요소와 4번째 요소를 비교합니다.

 

33이 10보다 더 크네요.

 

두 수의 위치를 바꾸면서 10을 정렬된 셋에 삽입합니다.

 

이제 정렬된 셋 안에서 또 비교를 하여 10이 앞에 있는 수 들보다 큰 지를 확인합니다. 그런데 27이 10보다 앞에 있네요.

 

10과 27의 위치를 바꿔 줍니다.

 

그런데 10 앞에 아직 10보다 큰 14가 존재합니다. 

 

14와 10의 위치를 또 바꾸어 줍니다.

 

이제 정렬된 셋이 정말로 정렬된 셋이 되었네요. 여기까지가 삽입 정렬의 3단계를 거친 겁니다. 

 

삽입 정렬은 정렬해야하는 데이터 셋에 있는 총 요소의 개수를 n이라고 할 때 n-1 번의 단계를 거쳐야 합니다. 

 

그리고 각 단계를 거칠 때마다 정렬된 셋에서 또 정렬을 하게 되죠. 

 

따라서, 삽입 정렬의 시간 복잡도는 버블 정렬과 마찬가지로 Ο(n²) 입니다. 

그렇기 때문에 정렬해야할 데이터의 양이 많은 경우에 사용하시면 안됩니다. 

데이터 양이 증가함에 따라 소요되는 시간이 제곱으로 늘어날 테니까요.

 

자, 앞서 버블 정렬에 대해서도 얘기를 해봤으니 버블 정렬과 삽입 정렬의 차이점이 뭔가에 대해서 한번쯤 생각해보고 넘어가는게 좋겠죠?

 

버블 정렬 vs. 삽입 정렬 ( Bubble Sort vs. Insertion Sort )

 

버블 정렬은 두 개의 요소(데이터)를 비교해서 위치를 바꿔주고, 그 다음 두 개의 요소를 비교하고 바꿔주고, 또 그 다음 두 개의 요소를 비교하고 바꿔주는 식으로 진행이 되었었죠? 그렇게 한번의 싸이클을 다 돌았을 때 순서가 바뀐 것이 있으면 한 번 더 싸이클을 돌게 됩니다. 순서가 바뀐 것이 없으면 완벽히 정렬되었다고 생각하고 알고리즘이 종료가 되죠.

 

자, 그런데 삽입 정렬은 어떤가요? 일단 두 개의 요소를 비교한 뒤에, 다음 두 개의 요소를 비교하기 전에 하는 일이 하나가 더 있죠. 바로, 정렬된 셋에 삽입된 데이터를 정렬하는 일입니다. 즉, 삽입 정렬은 현재 인덱스보다 작은 인덱스에 위치한 요소들이 모두 정렬되어 있다는 것을 보장해 줍니다.

 

시간 복잡도는 둘 다 Ο(n²)로 동일합니다.

 

이해가 되셨나요?? 이해가 잘 안 되셨으면 댓글 남겨주세요 정성껏 답해드리겠습니다. ^-^

 

저도 뭐 복습하면서 다시 정리를 해보려고 하는 거니까요, 여러분들이 "아~ 삽입 정렬이란게 이런 거구나~" 정도로 이해하실 수 있으면 제 목적은 달성한겁니다.

 

그럼 남은 시간 알차게 보내시고 활기찬 월요일을 맞이해 봅시당~ ^-^