[정렬 알고리즘] - 선택정렬 O(n²)

선택정렬

정렬되지 않은 대상 데이터의 최대 혹은 최소값을 데이터가 나열된 순으로 찾아가며 선택한다.

눈, 머리의 이해는 쉬우나 코드 구현이 복잡하다.

O(n²)의 비효율적인 시간복잡도 때문에 코딩테스트에서 빈번하게 나오지는 않음

BUT 문제의 일부로 사용될 수 있거나 기술 면접에서 질문의 대상이 될 수 있으므로 원리를 이해해야함

 

핵심이론

• 오름차순 : 최솟값 부터 선택
• 내림차순 : 최대값 부터 선택

정렬 형태에 따라 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞의 데이터와 Swap한다.

 

<그림 설명>

 

선택정렬 과정

1. 남은 정렬 부분에서 정렬형태(오름/내림)에 따라 최솟값, 최대값을 찾는다.
2. 남은 정렬 부분에서 가장 앞의 데이터와 선택된(최대/최소)값을 swap한다.
3. 가장 앞 데이터 위치를 변경함으로(index를 1 증가 ++) 남은 정렬 부분 범위를 축소한다.
   (LOOP마다 정렬된 부분에 포함된 가장 앞의 데이터들은 정렬된 데이터이므로)
4. 전체 데이터 크기만큼 index가 커질때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.

 

왜 n²일까?

버블 정렬과 마찬가지로 데이터의 갯수 5개 * loop 반복 횟수이다.

(n, n-1, n-2, n-3, n-4)