2.3 선택 정렬(Selection Sort)

이번에는 반복적인 방법으로 해결하는 선택 정렬(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회전 완료

…생략…