이번에는 반복적인 방법으로 해결하는 선택 정렬(Selection Sort) 알고리즘을 살펴볼게요.
선택 정렬도 순차 정렬처럼 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 차이점은 맨 앞의 원소를 최소값이 있는 위치로 설정한 후에 뒤에 원소들과 비교하여 더 작은 값을 발견하면 최소값의 위치를 바꾸는 거예요. 순차 정렬에서 원소를 교환했던 것과 다릅니다. 선택 정렬은 내부 반복문을 수행한 후에 최소값과 맨 앞의 원소와 교환해요.
선택 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
min=i
반복(j:=i+1->n)
조건(compare(base[min], base[j]) > 0)
min := j
교환(base[i],base[min])
예:
2 9 4 1 5 6 8 3 7 (정렬 전, n:9)
2 9 4 1 5 6 8 3 7 (i:0, j:1, min:0)
2 9 4 1 5 6 8 3 7 (i:0, j:2, min:0)
2 9 4 1 5 6 8 3 7 (i:0, j:3, min:3) – min 변경
2 9 4 1 5 6 8 3 7 (i:0, j:4, min:3)
2 9 4 1 5 6 8 3 7 (i:0, j:5, min:3)
2 9 4 1 5 6 8 3 7 (i:0, j:6, min:3)
2 9 4 1 5 6 8 3 7 (i:0, j:7, min:3)
2 9 4 1 5 6 8 3 7 (i:0, j:8, min:3)
1 9 4 2 5 6 8 3 7 (i:0, j:8, min:3) – 교환, 1회전 완료
1 9 4 2 5 6 8 3 7 (i:1, j:2, min:2) – min 변경
1 9 4 2 5 6 8 3 7 (i:1, j:3, min:3) – min 변경
1 9 4 2 5 6 8 3 7 (i:1, j:3, min:4)
1 9 4 2 5 6 8 3 7 (i:1, j:3, min:5)
1 9 4 2 5 6 8 3 7 (i:1, j:3, min:6)
1 9 4 2 5 6 8 3 7 (i:1, j:3, min:7)
1 9 4 2 5 6 8 3 7 (i:1, j:3, min:8)
1 2 4 9 5 6 8 3 7 (i:1, j:3, min:8) – 교환, 2회전 완료
1 2 4 9 5 6 8 3 7 (i:2, j:3, min:2)
1 2 4 9 5 6 8 3 7 (i:2, j:4, min:2)
1 2 4 9 5 6 8 3 7 (i:2, j:5, min:2)
1 2 4 9 5 6 8 3 7 (i:2, j:6, min:2)
1 2 4 9 5 6 8 3 7 (i:2, j:7, min:7) – min 변경
1 2 4 9 5 6 8 3 7 (i:2, j:8, min:7) – min 변경
1 2 3 9 5 6 8 4 7 (i:2, j:8, min:7) – 교환, 3회전 완료
…생략…