자료 구조와 알고리즘
배열 29, 10, 14, 37, 13을 선택 정렬(정렬되지 않은 부분에서 최솟값을 찾아, 정렬되지 않은 부분의 맨 앞과 교환한다)로 오름차순 정렬한다. 이 조작을 2회 수행한 후의 배열은?
- A10, 13, 14, 37, 29
- B10, 14, 29, 37, 13
- C10, 14, 13, 29, 37
정답과 해설 보기
정답: A. 10, 13, 14, 37, 29
1회째는 전체의 최솟값 10을 맨 앞의 29와 교환하여 10, 29, 14, 37, 13이 됩니다. 2회째는 두 번째 이후의 최솟값 13을 두 번째의 29와 교환하여 10, 13, 14, 37, 29가 됩니다. 선택 정렬의 비교는 항상 n(n−1)/2회이지만, 교환은 1회의 조작에 최대 1회이므로 쓰기 비용이 큰 데이터에서 유리한 경우가 있습니다. 10, 14, 29, 37, 13은 삽입 정렬로 원소 2개를 끼워 넣은 후, 10, 14, 13, 29, 37은 버블 정렬을 2패스 수행한 후의 배열입니다.