선택 정렬(Selection Sort)

🟩 입력 배열에서 가장 작은 값부터 순서대로 '선택'해서 나열하는 방식

수열 중에서 최솟값을 찾아 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복한다.

최솟값을 찾을 때는 선형 탐색을 사용

 

SelectionSort(A[ ], n) {
	for (i=0; i< n-1; i++) { // (n-1)번 반복
		min = i;
		for (j=i+1; j < n; j++) // ①A[i..n-1]에서 최솟값 찾기
			if (A[min] > A[j])
				min = j;
        A[i]와 A[min]의 자리바꿈; // ②최소값과 A[i]의 위치 교환
    }
	return (A);
}

 

 

🟩 시간복잡도

총 비교횟수 = (n-1) + (n-2) + ... + 1 = n(n-1)/2 👉 O(n^2)

루프i	0	1	2	...	n-2
루프j의 비교횟수	n-1	n-2	n-3	...	1