삽입정렬(Insertion Sort)

Goal

      - Insertion Sort 에 대해 설명할 수 있다.

      - Insertion Sort 과정에 대해 설명할 수 있다.

      - Insertion Sort를 구현할 수 있다.

      - Insertion Sort의 시간 복잡도를 계산 할 수 있다.

---

1. Insertion Sort Summary

   

     '각 숫자를 적절한 위치에 삽입하는 방법'

     '다른정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입정렬은 필요할때만 위치를 바꿈'

---

2.  Insertion Sort Process

     - 앞에있는 원소들이 이미 정렬이 되어있다고 가정

     - 앞에 원소들 자리에서 적절한 위치를 찾음

---

3.  Insertion Sort Coding

---

4. Insertion Sort 시간 복잡도

 

    장점

         

               - 삽입 정렬은 정렬이 되어있다고 가정 한다는점에서 특정한 경우에 굉장히 빠른속도를 낼수있다.

               - 데이터가 거의 정렬된 상태라면 어떤 알고리즘보다 빠르다.

 

    단점

   

               -  소스 코드 상에서 반복문이 두번 사용되기 때문에 O(N^2) 시간 복잡도를 가진다.