이번에는 반복 알고리즘을 이용하는 선택 정렬 알고리즘을 알아봅시다.
선택 정렬 알고리즘은 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘입니다. 물론 제일 작은 값을 찾아 맨 앞의 요소와 교체하는 방법을 반복할 수도 있습니다.
선택 정렬 알고리즘을 의사코드(pseudo code: 논리적인 수행 흐름을 이해할 수 있게 작성한 코드)는 다음과 같습니다.
선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
반복(max=0,j:=1; j<i ; j:=j+1)
조건(compare(base[max], base[j]) < 0)
max := j
temp: = base[i-1]
base[i-1] = base[max]
base[max] = temp
예:
정렬 전: 10 9 2 11 19
1.1회전: 10 9 2 11 19 (i:5, j:1, max:0)
1.2회전: 10 9 2 11 19 (i:5, j:2, max:0)
1.3회전: 10 9 2 11 19 (i:5, j:3, max:3)
1.4회전: 10 9 2 11 19 (i:5, j:4, max:4)
2.1회전: 10 9 2 11 19 (i:4, j:1, max:0)
2.2회전: 10 9 2 11 19 (i:4, j:2, max:0)
2.3회전: 10 9 2 11 19 (i:4, j:3, max:3)
3.1회전: 10 9 2 11 19 (i:3, j:1, max:0)
3.2회전: 2 9 10 11 19 (i:2, j:2, max:0 과 교환)
4.1회전: 2 9 10 11 19 (i:1, j:1, max:1)
선택 정렬 알고리즘도 버블 정렬 알고리즘처럼 이중 반복문으로 문제를 해결하는 알고리즘입니다.
내부의 반복문은 최대값이 있는 위치를 찾는 알고리즘입니다. 내부 반복문의 루프 변성은 j값이 점진적으로 증가한다는 것입니다. 그리고 루프 불변성은 인덱스 0에서 인덱스 j 사이의 요소 중에 max 인덱스에 최대값이 있다는 것입니다. 따라서 루프 변성과 루프 불변성을 통해 내부 반복문을 수행하면 max 인덱스에 최대값이 있다는 것을 증명할 수 있습니다. 그리고 외부 반복문의 루프 변성은 i값을 점진적으로 감소하는 것입니다. 그리고 루프 불변성은 인덱스 i 뒤의 요소들은 정렬 상태이며 i 앞의 요소의 값보다 크다는 것을 보장합니다. 따라서 루프 변성과 루프 불변성을 통해 정렬할 수 있음을 증명할 수 있습니다.