선택 정렬

선택 정렬은 배열의 부분 배열에서 최소값(또는 최대값)을 찾아 부분 배열의 시작 인덱스와 값을 교환하는 정렬 방법이다.

선택 정렬 알고리즘의 구체적인 과정은 다음과 같다.

1. 배열의 첫 번째 원소를 선택
2. 이후 원소들 중에서 최소값 검색
3. 최소값을 찾았다면, 해당 최소값을 현재 선택한 원소와 교환
4. 배열의 다음 원소를 선택하여 위 과정을 반복
5. 모든 원소에 대해 위 과정을 반복하여 정렬을 완료

	public class SelectionSort {
	public int[] sort(int[] arr) {
	for (int i = 0; i < arr.length-1; i++) {
	int min = arr[i];
	int index = i;
	for (int j = i+1; j < arr.length; j++) {
	if ( min > arr[j] ) {
	min = arr[j];
	index = j;
	}
	}
	int temp = arr[i];
	arr[i] = arr[index];
	arr[index] = temp;
	}
	return arr;
	}
	public static void main(String[] args) {
	SelectionSort selectionSort = new SelectionSort();
	System.out.println(Arrays.toString(selectionSort.sort(new int[]{7, 3, 8, 3, 6, 9, 4, 65, 89})));
	}
	}

view raw SelectionSort.java hosted with ❤ by GitHub

코드만 봐도 알수 있듯이 이 정렬법의 시간 복잡도는 O(n^2)이다. 

배열의 크기가 클수록 성능이 좋지 못하므로 일반적으로는 이보다 더 효율적인 정렬 알고리즘을 사용하게 된다.