선택 정렬(Selection Sort)

Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

Selection Sort와 Insertion Sort를 헷갈려하는 사람들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편하다.

 

import java.util.Arrays;

public class training2 {
	public static void main(String[] args) {
        int[] array = {30, 9, 10, 13, 14, 4, 7, 20};
		int temp;
        int min;
        for(int i=0; i<array.length-1; i++){ //1
			min = i;

            for(int j=i; j<array.length; j++){ //2
            	if(array[j]<array[min]){	  //3
			min = j;
                }    
            }
            temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
        System.out.println(Arrays.toString(array));
    }    
}

 

1. 우선, 위치(index)를 선택해준다.
2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작한다.
3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해준다.
4. '2'번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택한 위치(index)에 들어가야하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해준다.