삽입 정렬 : 이미 절렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식, 시간복잡도 = O(N^2)
1 ) 첫 번째 배열에서 첫 번째 인덱스만을 놓고 보았을 때 숫자가 하나 이기 때문에 정렬이 된 상태이다. 그럼 바로 다음 인덱스를 선택한다.
2 ) 선택된 인덱스의 값이 2이고 선택한 인덱스까지의 배열을 살펴보면 선택된 인덱스의 값이 5보다 작은 것을 알 수 있다. swap을 진행을 하고 다음 인덱스를 선택한다.
3 ) 현재 인덱스의 값은 4로 5보다는 작지만 2보다는 크므로 5랑만 swap을 진행하고 다음 인덱스를 선택한다.
4 ) 현재 인덱스의 값은 3으로 5와 4보다는 작지만 2보다는 크므로 5와 4를 순차적으로 swap하고 다음 인덱스를 선택한다.
5 ) 현재 인덱스의 값은 1로 앞선 모든 값들 보다 작으므로 순서대로 swap을 진행한다. 배열의 마지막 인덱스이므로 삽입 정렬을 종료한다.
삽입 정렬은 시간복잡도가 O(n^2)이므로 좋은 효율은 아닌 것 같다. 하지만 삽입 위치를 탐색하는 부분에서 이지 탐색 등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.
