선택정렬(SelectionSort)

- 선택 정렬

• 검색 범위에서 가장 작은 값을 찾아 왼쪽으로 이동시키는 정렬 방법이다.

• 버블 정렬 처럼 2중 for 문을 사용하기 때문에 시간 복잡도는 O(n^2)이며 그렇기 때문에 계산하는 시간이 느리다.

• 선택 정렬은 시간복잡도는 버블 정렬과 동일하지만 버블 정렬보다 성능이 좋다(조금)

public class SelectionSort {

	public static void selectionSort(int[] list) {
	    int indexMin, temp;

	    for (int i = 0; i < list.length - 1; i++) {
	        indexMin = i;	// 범위중 가장 작은값 index
	        for (int j = i + 1; j < list.length; j++) {
	            if (list[j] < list[indexMin]) { // 부호를 바꾸면 내림 차순이 된다.
	                indexMin = j;
	            }
	        }
	        temp = list[indexMin];	 	// 가장 작은값을 기억한다.
	        list[indexMin] = list[i]; // 자장 작은 값과 왼쪽 시작 index 와 swap 한다.
	        list[i] = temp; 	// 왼 쪽부터 가장 작은 값을 배치한다.
	        System.out.println(Arrays.toString(list));
	    }
	    
	    System.out.println("결과 : " + Arrays.toString(list));
	}
    
    
	public static void main(String[] args) {
		int[] arr = {1 ,4, 2, 8, 10, 7, 3, 9, 5, 6};
		selectionSort(arr);
	}
}

[1, 4, 2, 8, 10, 7, 3, 9, 5, 6]
[1, 2, 4, 8, 10, 7, 3, 9, 5, 6]
[1, 2, 3, 8, 10, 7, 4, 9, 5, 6]
[1, 2, 3, 4, 10, 7, 8, 9, 5, 6]
[1, 2, 3, 4, 5, 7, 8, 9, 10, 6]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 7]
[1, 2, 3, 4, 5, 6, 7, 9, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
결과 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]