| r2 ➤ r3 | |
| 36 | 의사코드 1을 보자. 선택 정렬의 수행 시간은 모든 경우에 [math(\Theta(n^2))]이다. for 루프는 [math(n-1)]번 순환하고, index 교환은 상수 시간이 든다. 큰 수를 찾는 것은 작업은 부분 배열의 크기에 비례한다.[* 크기가 k인 배열에서 가장 큰 수를 찾는 데는 [math(k-1)]번의 비교가 필요하다.] 부분 배열의 크기는 for문에서 n부터 시작하여 2까지 감소한다. 그러므로 비교하는 총 횟수는 [math((n-1)+(n-2)+…+1=\dfrac{n(n+-1)}{2})], 즉 [math(\Theta(n^2))]이다. |
