[디딤돌 C언어 자료구조와 알고리즘] 2.3 선택 정렬 알고리즘

2. 3 선택 정렬 알고리즘

 이번에는 반복 알고리즘일 이용하는 선택 정렬 알고리즘을 알아봅시다.

 

 선택 정렬 알고리즘은 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘입니다. 물론 제일 작은 값을 찾아 맨 앞의 요소와 교체하는 방법을 반복할 수도 있습니다.

 

 선택 정렬 알고리즘을 의사코드(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 앞의 요소의 값보다 크다는 것을 보장합니다. 따라서 루프 변성과 루프 불변성을 통해 정렬할 수 있음을 증명할 수 있습니다.

2.3.1 선택 정렬 알고리즘 성능 분석

2.3.2 선택 정렬 알고리즘 구현