삽입 정렬의 분석 (상황별 시간복잡도 확인)
2019. 10. 5.
삽입 정렬 분석하기 ko.khanacademy.org 삽입 정렬의 분석 선택 정렬과 삽입 정렬은 배열의 인덱스를 통해 반복합니다. 삽입 정렬의 경우 1, 2, 3, ... , n-1의 요소에서 insert()를 호출합니다. 이는 선택 정렬의 함수였던 IndexOfMinimum()처럼 하위 배열의 크기에 따라 수행 시간이 달라지는 것과 비슷합니다. 즉, insert를 수행하는데 있어서 선택정렬만큼 시간이 걸린다는 의미입니다. 하지만, 경우에 따라서 훨씬 빠르게 정렬 되는 경우도 있습니다. insert()를 호출하고 하위 배열에 삽입되는 값이 하위 배열의 모든 요소보다 작을 때를 가정해봅니다. 예를 들어 [2,3,5,7,11] 이라는 배열에서 0을 삽입하게 될 경우, 하위 배열의 모든 요소가 오른쪽으로 하나..