선택 정렬 Selection Sort

Intro

선택 정렬의 이해

선택 정렬(Selection Sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

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

2.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

3.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

n개의 주어진 리스트를 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. ¹

비교 횟수

교환 횟수

T(n)=(n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n²)

시간 복잡도 O(n²)인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다

장점 : 자료 이동 횟수가 미리 결정된다. (메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다)

단점 : 안정성을 만족하지 않는다. 값이 같은 레코드가 있는 경우 상대적인 위치가 변경될 수 있다.