Page 209 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 209
06-3 단순 선택 정렬
단순 선택 정렬(straight selection sort)은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순
서대로 정렬하는 알고리즘입니다.
단순 선택 정렬
아래의 배열에 단순 선택 정렬 알고리즘을 적용해 보겠습니다. 이 알고리즘은 가장 작은 요소부
터 정렬하는 알고리즘이기 때문에 가장 작은 값의 요소인 1을 선택해 정렬을 시작합니다.
6 4 8 3 1 9 7
1을 6과 교환합니다. 교환한 다음의 배열 상태는 아래와 같습니다.
1 4 8 3 6 9 7
가장 작은 요소인 1이 맨 앞으로 왔습니다. 이어서 두 번째로 작은 요소인 3을 선택해 정렬합니
다. 3을 4와 교환하면 아래처럼 두 번째 요소의 정렬이 끝납니다.
1 3 8 4 6 9 7
아래 그림은 앞에서 진행한 것과 같은 작업을 반복하는 모습을 나타낸 것으로, 아직 정렬하지
않은 부분에서 값이 가장 작은 요소를 선택하고 아직 정렬하지 않은 부분의 첫 번째 요소와 교
환합니다.
０ １ ２ ３ ４ ５ ６
6 4 8 3 1 9 7
아직 정렬하지 않은 부분의 첫 번째 요소
1 4 8 3 6 9 7
아직 정렬하지 않은 부분에서
값이 가장 작은 요소
1 3 8 4 6 9 7
1 3 4 8 6 9 7
정렬을 마침 아직 정렬하지 않음
1 3 4 6 8 9 7
1 3 4 6 7 9 8
1 3 4 6 7 8 9
[그림 6-10] 단순 선택 정렬 과정
06•정렬 209
