4-2 선택 정렬

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

시간 복잡도 O(n^2)으로 느린 편

 

핵심

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

 

선택 정렬 과정

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

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

3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 부분의 범위를 축소한다.

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

 

시간복잡도가 O(n^2)인 이유를 생각해보자.

데이터의 개수가 n개 일때,

첫 번째 루프에서 비교횟수는 1~ n-1번으로 n-1번

두 번째 루프에서 비교횟수는 2~n-1번으로 n-2번

반복하면

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

이므로, 시간복잡도가 O(n^2)가 된다.