[lecture] 6주차.정렬 알고리즘_선택 정렬

수업을 듣고 정리한 내용입니다.

선택 정렬(Selective sort)

입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선ㅌ개하여, 배열 1번 원소와 자리를 바꾸는 방식을 통해 마지막에 2개의 원소 중 작은 것을 선택해 자리를 바꾼다. 이렇게 최솟값을 선택해 정렬하는 것을 선택 정렬이라고 한다.

선택 정렬 방식은 아래 > 우측 방향으로 진행된다.

//selective sort
입력 : 크기가 n인 배열
출력 : 정렬된 배열 A
for i=0 to n-2
	min = i
    	for j=i+1 to n-1	//A[i] ~ A[n-1]에서 최솟값을 가짐
        	if A[j] < A[min]
            	min = j
            A[i] <-> A[min]	//min이 최솟값이 있는 원소의 인덱스임
return A

시간복잡도

코드의 외부for루프는 (n-1)번 수행하고, 내부 루프는 (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2 번 수행하게 된다. 루프 내부의 if 조건이 true일 때의 자리 바꾸는 시간 복잡도는 O(1)이다. 따라서 n(n-1) / 2 * O(1) = O(n^2)이다.

선택 정렬의 특징

1. 입력이 거의 정렬되든, 역으로 정렬되든, 랜덤하게 되어 있든 항상 일정한 시간 복잡도를 나타낸다.

2. 입력에 민감하지 않은(input insensitive) 알고리즘이다.

3. 원소 간의 자리바꿈 횟수가 최소인 정렬이다.