정렬 알고리즘(Sorting Algorithm)의 모든 것 ② - 선택정렬(Selection Sort)

2. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ② - 선택정렬

: 선택 정렬(Selection Sort)은 다음과 같은 순서로 이루어진다. (출처 - 위키백과)

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

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

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

- 선택정렬 역시 버블 정렬과 동일하게 최악의 경우일 때 O(n^2)만큼의 시간복잡도를 갖는다.

- 버블정렬과 동일하게 쉬운 개념의 알고리즘이며, 사용할 수 있는 메모리가 제한적인 경우에 사용 시 성능 상의 이점이 있을 수 있다.

<< 선택 정렬 C++ 코드 >>

인덱스 크기가 9이고 각 인덱스에 정렬되지 않은 정수가 들어있는 배열이 있다고 했을 때,

이런식으로 마지막 하나의 원소가 남을 때 까지 반복하다 보면 정렬이 되어 있다.

<< 선택 정렬의 특징 >>

 * 장점 

- 자료 이동 횟수가 미리 결정된다.

- 이해하기 쉬운 개념이다

* 단점

- 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

<< 선택정렬의 시간복잡도 >>

- (n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1 = n(n-1) / 2

- T(n) = O(n^2)

- 버블정렬과 같은 O(n^2)이지만 퍼포먼스는 선택정렬이 더 낫다.