선택 정렬(Selection sort)

지난 포스팅에서 정렬에 대해 알아보았습니다. 이번 포스팅부터 각 정렬의 정의와 원리, 

그리고 성능 분석을 하여 시간복잡도를 빅오 표기법으로 표현해보겠습니다.

선택 정렬(selection sort)은 정렬 되지 않은 데이터들에 대해 

가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 

위 그림은 위키백과에 있는 선택 정렬 애니메이션 모습이다.

선택 정렬의 순서를 설명하자면

1. 주어진 리스트 중 최소 값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다.

3. 가장 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체한다.

이러한 과정을 반복하여 수행하게 된다.

위 그림을 보면 더 이해하기 쉬울 것이다.

좌측에 노란 리스트는 이미 정렬이 완료 된 리스트이고, 우측에 파란 리스트는 정렬이 되지 않은 리스트이다.

우측에 정렬이 되지 않은 파란 리스트에서 최소값을 선택하여

좌측 노란 리스트로 넘겨 준다고 생각하면 이해가 쉬울 것이다.

위 그림은 선택 정렬 함수 소스 코드이다.

직접 소스 코딩을 해봐야 이해가 쉽고, 머리 속에 기억도 남아

소스코드를 올리지 않으려 했으나, 시간 복잡도 설명을 위해 올리게 되었다.

for문의 실행 횟수를 따져보면 외부 루프는 (n-1)번, 내부는 (n-1)-i 번 반복되는 것을 확인 할 수 있다.

그러므로 전체 비교 횟수는

(n-1) + (n-2) + (n-3) + ... + 1 이므로 n(n-1)/2 이다.

빅오 표기법으로 나타내면  이다.

이상으로 선택 정렬의 원리와 개념, 효율성에 대해 알아 보았습니다.

다음 포스팅에서는 삽입 정렬(Insertion sort)에 대해 알아 보겠습니다.