선택 정렬 Selection Sort

Intro::

선택 정렬 Selection Sort에 대해 알아보자.

정의

위치를 선택하고, 그에 알맞는 수를 넣는 알고리즘이다.

1. 최소값을 찾는다.

2. 지정된 위치(맨 앞에서 부터 뒤로 밀린다.)에 값을 넣어준다.

시간복잡도

n(n-1)/2 ⇒ O(n^2) 이다.

코드

package algorithm;

import java.util.Arrays;

public class SelectionSort {
	public static void main(String[] args) {
		int[] arr = {6, 2, 1, 4, 5, 3};
		for (int idx = 0; idx < arr.length - 1; idx++) {
			int target = idx;
			for (int i = idx + 1; i < arr.length; i++) {
				if (arr[i] < arr[target]) {
					target = i;
				}
			}
			int tmp = arr[idx];
			arr[idx] = arr[target];
			arr[target] = tmp;
			System.out.println(idx + 1 + "회전: " + Arrays.toString(arr));
		}
	}
}



/*
1회전: [1, 2, 6, 4, 5]
2회전: [1, 2, 6, 4, 5]
3회전: [1, 2, 4, 6, 5]
4회전: [1, 2, 4, 5, 6]
5회전: [1, 2, 4, 5, 6]
*/

References::