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

선택 정렬(Selection Sort)

- 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고,

  다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여, 배열의 1번 원소와 자리를 바꿈

  >> 마지막에 2개의 원소 중 작은 것을 선택하여 자리를 바꿈

 

알고리즘

입력: 크기가 n인 배열 A

출력: 정렬된 배열 A

for i=0 to n-2
	min = i
    	for j=i+1 to n-1
        	if A[j] < A[min]
            	min=j
        A[i] <-> A[min]
return A

 

시간 복잡도

외부 for루프는 (n-1)번 수행

-i=0일 때 내부 for루프는 (n-1)번 수행

-i=1일 때 내부 for루프는 (n-2)번 수행

...

-마지막으로 1번 수행

 

내부의 for루프가 수행되는 총 횟수

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

 

루프 내부의 if조건이 True일 때의 자리바꿈 O(1)

 

n(n-1)/2*O(1)=O(n^2)

 

특징

- 항상 일정한 시간 복잡도를 나타냄

- 입력에 민감하지 않은(input insensitive) 알고리즘

- 원소 간의 자리바꿈 횟수가 최소인 정렬