16.자료가 다음과 같을 때, 삽입(insertion) 정렬 방법을 적용하여 오름차순으로 정렬할 경우 pass 2를 수행한 결과는?

해설

위 자료들을 insertion sort 할 경우 pass 1 : (8 3) 4 9 7 -> (3 8) 4 9 7 pass 2 : 3 (8 4) 9 7 -> (3 4) 8 9 7 insertion sort는 두 수의 크기를 비교해서 조건에 따라 스왑하는 과정을 제일 앞부터 제일 뒤까지 한 다음(n-1회) 그 과정을 자료의 개수의 n-1번만큼 반복한다. 즉 O(n^2)의 time complexity를 가진다.