[알고리즘] 정렬 - 선택정렬

선택정렬

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법

특징

• 구현이 복잡하다.
• 배열이 미정렬 상태이므로 최소값 검색에는 이진 검색이 아닌 선형 검색 알고리즘을 사용한다.
• 선택 정렬은 버블 정렬보다 빠르다.

시간복잡도

O(n^2) : 비효율적
-> 코테에서는 많이 사용하지않음

핵심 이론

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap

과정

1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다
4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.

-> 선택정렬 자체를 묻는 문제는 잘 안나오지만, 이 원리를 응용하는 문제는 나올 수 있음!
어떤 원리로 동작하는지 잘 알아두기!