[알고리즘] 선택정렬

 

선택 정렬

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

구현 방법이 복잡하고 시간복잡도가 O(N^2)로 효율적이지 않음

 

선택 정렬 과정

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

 

① 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다

② 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap

③ 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소

④ 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복

 

선택 정렬 시간복잡도 구하기

선택정렬을 하기 위한 데이터가 n개일 때

n개 탐색

n-1개 탐색

n-2개 탐색

n-3개 탐색

...

n-n개 탐색

 

▶ 총 n^2만큼 탐색

 

 

관련 문제보기

백준 1427번 소트인사이드