정렬6) 삽입 정렬(Insertion Sort)

* 삽입 정렬
- 앞으로 가면서 탐색을 진행
- n크기의 배열 탐색을 index 1번부터 진행


* 시간 복잡도
- 삽입 정렬은 최악의 경우와 최선의 경우 시간 차이가 많다

- 최악의 경우

    try1: 1
    try2: 2
      ...
    try(n-1): n-1
    - 총 탐색 수 = n(n - 1)/2
    - O(n^2)

- 최선의 경우(정렬 완료된 경우)
    - 총 탐색 수 = n 번
    - O(n)