📚 Selection Sort

선택 정렬. 대표적인 O(n^2) 정렬 알고리즘 셋 중 하나이다.
개념은 그냥 배열을 순회하며 최솟값을 찾아 앞에서부터 채워나간다.

💻 Implementation

class SelectionSort {
	public static void main(String[] args) {
		int[] arr = {6, 3, 1, 7, 2};
		int min, tmp;
		for (int i=0;i<arr.length;i++) {
			min = i;
			for (int j=i+1;j<arr.length;j++)
				if (arr[j] < arr[min])
					min = j;
			tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
		for (int i=0;i<arr.length;i++)
			System.out.print(arr[i] + " ");
	}
}

머.. 간단하다.

⌛️ Time Complexity

O(n^2). 하지만 Bubble, Insertion, Selection 세 정렬 알고리즘 중에 평균적으로 가장 오랜 시간이 걸린다. Best case와 worst case 상관없이 배열을 n^2번 순회하기 때문.

Is this stable?

stable하지 않다. 떨어진 요소들 사이에 교환이 일어나기 때문에, [2,2,1] 의 배열을 정렬하려 하면 2의 순서가 보장되지 않는다.