선택정렬(Selection Sort)

선택정렬(Selection Sort)는 원리가 가장 간단한 정렬 알고리즘 중의 하나다. 우선 배열 A[1...n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경쓰지 않아도 된다. 이 원소는 정렬이 끝났다고 볼 수 있으므로 이제 이 원소를 제외한 나머지 원소들로 같은 작업을 반복하면 된다.

간결하게 나타내면 

각 루프마다

• 최대 원소를 찾는다.
• 최대 원소와 맨 오른쪽 원소를 교환한다.
• 맨 오른쪽 원소를 제외한다.

하나의 원소만 남을 때까지 위의 루프를 반복한다.

예를 들면, 정렬하고자 하는 배열(Initial array)에서 가장 큰 수(37)을 찾아 배열의 맨 끝 원소인 13과 자리를 바꾸고 잊어버린다. 그 다음 다시 가장 큰수(29)를 찾아 배열의 맨 끝 원소인 13과 자리를 바꾸고 잊어버린다. 다시 가장 큰 수(14)는 배열의 맨 끝에 위치해 있으므로 아무런 작업을 하지 않고 잊어버린다. 그리고 다시 가장 큰수(13)을 배열의 맨 끝 원소 10과 자리를 바꾸면 배열의 모든 원소들이 정렬이 완료된다.

선택정렬(Selection Sort)의 슈도코드는 다음과 같다.

선택정렬의 수행시간을 살펴보면

①의 for 루프는 n-1번 반족

②에서 가장 큰 수를 찾기 위한 비교횟수 : n-1, n-2, .... , 2, 1

③의 교환은 상 수 시간 작업

따라서 선택정렬의 시간복잡도는 다음과 같다.

T(n) = (n-1) + (n-2) + ... + 2 + 1 = O(n^2) 이다.