이번에는 선택 정렬 알고리즘을 분석해 보기로 해요.
선택 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
min=i
반복(j:=i+1->n)
조건(compare(base[min], base[j]) > 0)
min := j
교환(base[i],base[min])
선택 정렬 알고리즘을 보면 반복문 내부에 반복문이 있는 구조입니다. 먼저 내부의 반복문에서 하는 일이 무엇인지 알아봅시다.
선택 정렬 알고리즘의 내부 반복문에서는 j값을 i+1부터 시작하여 n까지 순차적으로 증가하며 작업을 수행하죠. 따라서 루프 변성은 j값이 변하는 것이예요. 그리고 배열의 min번째 요소와 j번째 요소와 비교하여 j번째 요소가 작으면 min을 j로 변경해요. 이처럼 수행하면 배열의 i번째 요소부터 j번째 요소 중에서 제일 작은 값이 있는 위치는 min이죠. 따라서 루프 불변성은 배열의 i번째 요소부터 j번째 요소 중에서 제일 작은 값은 min에 있다는 것이예요.
루프 변성인 j값이 n까지 변하는 특징과 루프 불변성인 배열의 i번째 요소부터 j번째 요소 중에서 제일 작은 값은 min에 있다는 것으로 내부 반복문을 수행하면 i번째 요소부터 맨 뒤에 요소 중에 제일 작은 값이 있는 위치는 min이라는 것이예요.
이번에는 내부 반복문을 감싸고 있는 외부 반복문을 살펴보아요. i는 0에서 n까지 1씩 증가하고 있어요. 내부 반복문을 수행하면 제일 작은 값이 min에 있죠. 그리고 i번째 요소와 교환을 하고 있어요. 결국 i번째 이후에 요소들은 i보다 큰 값들만 있겠죠. 따라서 i가 변하는 루프 변성과 i이전의 요소들은 정렬 상태이고 i 뒤에 있는 요소들보다 작다는 루프 불변성으로 외부 반복문을 수행하면 정렬할 수 있다는 것을 증명할 수 있어요.
이번에는 선택 정렬 알고리즘 성능을 분석합시다.
선택 정렬의 내부 반복문의 수행 시간을 S(i)라고 가정할게요. 내부 반복문은 j가 i+1에서 n까지 순차적으로 증가하므로 비교를 n-i번 수행함을 알 수 있어요. 따라서 S(i)= n-i죠.
외부 반복문은 i가 0에서 n까지 순차적으로 증가하면서 내부 반복문을 수행하고 교환 1회합니다. 수행 시간을 T(n)이라 가정하면 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 이죠.
따라서 T(n) = S(0)+1 + S(1)+1 +S(n-2)+1 … +S(n-1)+1 = n+1 + n + n-1 + …+1
따라서 T(n)= n(n+1)/2 이고 점근식 표기에서 높은 차수의 항만 남고 상수를 버리므로 O(n^2)라고 할 수 있습니다. 선택 정렬도 순차 정렬과 거품 정렬처럼 O(n^2)이네요.
하지만 교환하는 시간은 O(n)이라는 차이가 있어요. 물론 전체 성능에 미치는 영향은 아주 작아요.