[개념정리] 선택정렬

[YubinShin]

선택정렬

selection sort
대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법입니다.
구현 방법이 복잡하고, 시간복잡도도 커서 코딩테스트에서 직접적으로 사용하진 않습니다.
다만 문제의 일부로 나오거나, 기술면접에서 선택정렬이나 삽입정렬 원리에 관한 질문이 나오기도 합니다.

시간복잡도

O(n²)

예를 들어 n이 5라고 할때 n-1, n-2, n-3, n-4, n-5 이걸 n번 반복한다. 그래서 최악의 경우를 산정할 때 앞의 상수를 빼고 n² 이 나온다.

원리