정렬, 선택정렬 알고리즘

알고리즘설명

<img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/RYUI62181224235510.PNG" style="width:240px">

전체 배열에서 가장 작은 숫자를 찾아 **"선택"**하여 첫 번째 위치에 둔다.

그후 두번째 부터 마지막까지의 배열에서 두 번째로 작은 숫자를 찾아 **"선택"**하여 두번째 위치에 둔다.

이를 반복한다.

<br/>

<span style="color:#000000">복잡도

<span style="color:#000000">첫번째에는 n번을 순회한다.

<span style="color:#000000">두번째에는 n-1번을 순회한다.

<span style="color:#000000">세번째에는 n-2 번을 순회한다.

<span style="color:#000000">..

<span style="color:#000000">마지막에는 n-(n-1)을 순회한다.

<span style="color:#000000">모든 시간 복잡도는 n+ (n-1) + (n-2) + ..... + (n-(n-1)번이므로 n*(n-1)/2가 된다.

<span style="color:#000000">복잡도는 O(N^2)이다.

<br/>

장단점

데이터 이동이 비교적 적은 것이 장점이다.

단점은 안정성을 만족하지 않는다. 즉 같은 값이 있을 경우 상대적 위치가 변경 될 수 있다.

<br/>

소스코드

public class SelectionSort {
	public void sort(int[] arr) {
		int n = arr.length;

		int min, temp;
		for (int i = 0; i < n - 1; i++) {
			min = i;
			for (int j = i; j < n; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}

			temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}

	public static void main(String[] args) {
		int arr[] = { 10, 8, 7, 3, 2, 15 };
		new SelectionSort().sort(arr);
		System.out.print(Arrays.toString(arr));
	}

}

<br/>