선택 정렬 (Selection Sort)

소개

• 배열을 조회하면서 현재 위치에 들어갈 값 (남은 숫자들 중 가장 크거나 작은 값) 을 찾아 정렬한다.

 

 

과정

 

 

코드

• 현재 위치 \(i\) 값과 배열의 나머지 모든 값을 비교하여 가장 작은 값을 가진 인덱스 \(idx\) 를 \(j\)로 갱신한다.
• 두 번째 for문이 끝나면 \(i\)와 \(idx\) 위치의 값을 바꾼다.

public static void main(String[] args) {
	int[] nums = { 8, 5, 2, 6, 9, 4, 1, 3, 0, 7 };
	int len = nums.length;

	for (int i = 0; i < len - 1; ++i) {
		int minIdx = i;

		for (int j = i + 1; j < len; ++j) {
			if (nums[minIdx] > nums[j]) {
				minIdx = j;
			}
		}

		if (arr[minIdx] < arr[i]) {
			Swap(nums, minIdx, i);
		}
	}
}

 

 

결과

 

 

계산 복잡도

Time Complexity : for문 두 개가 지배하며, \((N-1) + (N -2 ) + ... + 1 = \frac{(N-1)*(N)}{2}\)

• Best : \(O(N^2)\)
• Average : \(O(N^2)\)
• Worst : \(O(N^2)\)

Space Complexity : \(O(1)\)