선택정렬(Selection Sort)

 

문은영 교수님의 데이터구조 수업 자료입니다. 문제시 삭제하겠습니다.

방식

i번째(0부터 시작) iteration에서 0 ~ i-1 까지는 정렬되어있음이 보장된다.

이때 i ~ n 까지의 entry 중에 가장 작은 값을 a[i]와 교환한다.

구현할 때 entry 범위가 헷갈릴 수 있다. arr[0]에 가장 작은 값이 들어가는 것이 보장되어야함을 기억하면 덜 헷갈린다.

 

시간 복잡도

Avg - O(n^2)

ith iteration에서 n-i 개의 entry 중 가장 작은 값을 찾는데에는 평균 (n-i)/2 의 비용이 든다.

i가 1부터 n까지 이므로 평균 시간복잡도는 T(n) = (탐색) + (교환) = ( 0+…+n-1 ) / 2 + ( 1 * n )이고

O(T(n)) = O(n^2) 이다.

 

Best - O(n^2)

이미 정렬되어있는 경우에도 가장 작은 값임을 보장하려면 모든 값을 다 봐야한다.

따라서 시간 복잡도는 여전히 O(n^2) 이다.

 

Worst - O(n^2)

역순으로 정렬된 경우 각 iteration마다 항상 n-i 개의 원소를 탐색해야한다.

따라서 시간복잡도는 Avg와 같은 O(n^2)이다.

 

증명

Selection sort의 결과가 정말 정렬되는게 맞는가

i = 0 일때 arr[0] 에는 해당 배열에서 1 번째로 작은 원소가 들어온다.

 

i = 1 일 때 arr[1]에 1번째나 3번째로 작은 원소가 들어올 수 있을까?

이미 1번째로 작은 원소는 탐색하는 entry의 범위에서 벗어났고,

arr[1]에 3번째로 작은 원소가 들어오려면 2번째로 작은 원소 > 3번째로 작은 원소 라는 식이 성립해야하는데 이는 모순이다.

따라서 arr[1]에는 2 번째로 작은 원소가 들어가게 된다.

 

i = k인 경우는 어떨까? 이미 0 ~ k-1 entry에 1번째로 작은 원소부터 k번째로 작은 원소가 포함되어있어서 이들은 arr[k]에 들어올 수 없다. 그렇다고 k+2번째로 작은 원소가 들어올 수도 없다. k+2번째로 큰 원소는 항상 k+1번째로 작은 원소보다 작기 때문이다.

arr[k]에 항상 k+1번째로 작은 원소가 들어오는 것이 보장되기 때문에, arr[k] < arr[k+1] 은 0부터 n-1까지의 범위의 모든 k에서 항상 참이다. 따라서 selection sort의 결과는 항상 올바르게 정렬되어있음을 보장할 수 있다.

 

참고 자료

유튜브 강의 : https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4