선택정렬(Selection Sort)

• 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
• 리스트를 정렬하려고 할 때 버블 정렬과 같은 O(n2)의 성능을 낸다.
• 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복한다. 

public class SortTest {
    @Test
    void select() {
//        int[] array = new int[]{5,9,3,1,2,8,4,7,6};
        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
//        int[] array = new int[]{9,8,7,6,5,4,3,2,1};

        int indexMin, temp;

        for (int i = 0; i < array.length - 1; i++) {
            indexMin = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[indexMin]) {
                    indexMin = j;
                }
            }
            temp = array[indexMin];
            array[indexMin] = array[i];
            array[i] = temp;
        }

        assertArrayEquals(array, new int[]{1,2,3,4,5,6,7,8,9});
    }
}​

 

시작 [5, 9, 3, 1, 2, 8, 4, 7, 6]

1. [1, 9, 3, 5, 2, 8, 4, 7, 6]
2. [1, 2, 3, 5, 9, 8, 4, 7, 6]
3. [1, 2, 3, 5, 9, 8, 4, 7, 6]
4. [1, 2, 3, 4, 9, 8, 5, 7, 6]
5. [1, 2, 3, 4, 5, 8, 9, 7, 6]
6. [1, 2, 3, 4, 5, 6, 9, 7, 8]
7. [1, 2, 3, 4, 5, 6, 7, 9, 8]
8. [1, 2, 3, 4, 5, 6, 7, 8, 9]

시작 [9, 8, 7, 6, 5, 4, 3, 2, 1]

1. [1, 8, 7, 6, 5, 4, 3, 2, 9]
2. [1, 2, 7, 6, 5, 4, 3, 8, 9]
3. [1, 2, 3, 6, 5, 4, 7, 8, 9]
4. [1, 2, 3, 4, 5, 6, 7, 8, 9]
5. [1, 2, 3, 4, 5, 6, 7, 8, 9]
6. [1, 2, 3, 4, 5, 6, 7, 8, 9]
7. [1, 2, 3, 4, 5, 6, 7, 8, 9]
8. [1, 2, 3, 4, 5, 6, 7, 8, 9]

시작 [1, 2, 3, 4, 5, 6, 7, 8, 9]

1. [1, 2, 3, 4, 5, 6, 7, 8, 9]