3-2 Insert Sort 구현, Big-O

Insert Sort에 구현과 함께 Big-O를 알아보겠습니다.

 

insert sort를 코드로 구현해봤습니다.

 

설명과 주석으로 한방에 이해하시는 분은 굉장히 훌륭하신 것 같습니다.

 

저는 이 로직을 print로 찍어봤습니다.

 

일단 코드를 포인트마다 출력되게 찍었고

얘를 출력해보면 아래와 같이 나옵니다.

 

 

저기 list : [] 라고 찍히는 부분에서, list에 있는 값을 하나씩 밀고, key의 값이 들어갈 위치를 찾아서 넣어주는 과정을 유심히 보시면 이해가 가장 빠르실 것 같습니다.

 

시간복잡도의 경우 2가지로 나뉘는데 best와 worst가 있습니다.

 

만약 [1,2,3,4,5] 라고 생긴 애가 있다면 중간에 list : 부분의 이동이 없기 때문에, O(n)이 가능하지만, 반대의 경우 O(n^2)이 됩니다.