[Algorithm] 선택 정렬 (Selection Sort)

선택 정렬

  선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나이다. 배열에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 원소와 자리를 바꾼다. 그러면 방금 맨 뒷자리로 옮긴 원소, 즉 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경 쓰지 않는다. 가장 큰 원소는 정렬이 끝났다고 볼 수 있으므로 이 원소를 제외한 나머지 원소들도 같은 작업을 반복하여 정렬한다.

 

선택 정렬의 작동 과정 (출처:쉽게 배우는 알고리즘)

선택 정렬 구현

public class SelectionSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{2, 3, 4, 5, 1, 8, 7, 6, 9};

        int max;
        int idx;
        int temp;

        for (int i = arrays.length - 1; i >= 0; i--) {
            max = arrays[i];
            idx = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arrays[j] > max) {
                    max = arrays[j];
                    idx = j;
                }
            }
            temp = arrays[i];
            arrays[i] = arrays[idx];
            arrays[idx] = temp;
        }
    }
}