210628 선택 정렬(selection sort)

선택 정렬 (selection sort) : 

• 제자리 정렬 알고리즘 중 하나
• 입력 배열 외의 다른 추가 메모리 필요 없음

1. 주어진 배열에서 최솟값 찾음 
2. 그 값을 맨 앞의 값과 교환함
3. 맨 처음 위치를 제외한 배열 범위에서 1~2번 반복

즉 1,2 번이 하나의 사이클로 한번 할때 마다 배열 내의 가장 작은 원소를 맨 앞으로 땡겨오는 작업을 n번하여 정렬하는 방법이다.

 

장 : 자료의 이동 횟수가 예상 가능함

단 : 불안정함, 값이 같은 레코드가 있는 경우에 상대적 위치가 변경될 수 있음

 

시간복잡도

 

배열의 크기 n 이라 하였을 때 

비교 횟수 : n-1, n-2, n-1, .... 2, 1 번 

교환 횟수 : 한 번 교환할 떄( swap 함수) 3번 => 최대 3(n-1) 번 

그러므로 

Best (모두 정렬되어 있는 상태) : 교환 X 비교만 O => 오메가(n^2)

Worst (역순 정렬) : 교환, 비교 최대로 => O(n^2)