문제
다음과 같은 방법으로 <보기>에 주어진 수열을 정렬할 때, 다섯 번째 교환이 이루어진 후의 수열은?
| 인접한 두 숫자의 크기를 비교하여 교환하는 방식으로 정렬한다. 이때 인접한 두 숫자는 수열의 맨 앞부터 뒤로 이동하며 비교된다. 맨 마지막 숫자까지 비교가 이루어져 가장 큰 수가 맨 뒷자리로 이동하게 되면 한 라운드가 종료된다. 다음 라운드는 맨 뒷자리로 이동한 수를 제외하고 같은 방식으로 비교 및 교환이 이루어진다. 더 이상 교환할 숫자가 없을 때 정렬이 완료된다. 교환은 두 개의 숫자가 서로 자리를 맞바꾸는 것을 말한다. |
<예 시>
| 다음은 ‘30 15 40 10’의 수열을 위의 방법으로 정렬한 것이다. 괄호는 각 단계에서 비교가 이루어지는 인접한 두 숫자를 나타낸다. ◦제1라운드 (30 15) 40 10 : 30 > 15 이므로 첫 번째 교환 15 (30 40) 10 : 40 > 30 이므로 교환이 이루어지지 않음 15 30 (40 10) : 40 > 10 이므로 두 번째 교환 15 30 10 40 : 가장 큰 수 40이 맨 마지막으로 이동 ◦제2라운드 (40은 비교 대상에서 제외) (15 30) 10 40 : 30 > 15 이므로 교환이 이루어지지 않음 15 (30 10) 40 : 30 > 10 이므로 세 번째 교환 15 10 30 40 : 40을 제외한 수 중 가장 큰 수 30이 40 앞으로 이동 ◦제3라운드 (30, 40은 비교 대상에서 제외) (15 10) 30 40 : 15 > 10 이므로 네 번째 교환 10 15 30 40 : 정렬 완료 |
<보 기>
| 37 82 12 5 56 |
① 5 12 37 56 82
② 37 12 82 5 56
③ 5 56 12 37 82
④ 12 37 5 56 82
⑤ 12 5 37 56 82
반응형
댓글