3-1 InsertSort 삽입정렬 원리

insert sort를 알아보겠습니다.

 

bubble sort 같은 경우에, 왼쪽에 있는 애를 오른쪽으로 계속 미는 느낌이었다면

 

insert sort 같은 경우에는 오른쪽애 있는 애를 왼쪽으로 민다는 느낌인 것 같습니다.

 

한번 아래의 예시를 보겠습니다.

자 얘를 가 보겠습니다.

 

2번째 애 부터 시작합니다.

 

 

13은 앞에 더 큰 항목이 없으니 그대로 있고

 

이동

또 이동

 

이렇게 하면 정렬이 끝납니다.

 

매우 쉽게 이해하셨을 것이라고 생각합니다.

 

그러면 이 과정을 코드로 표현하고, 시간복잡도를 알아보겠습니다.