[알고리즘] 선택정렬(Selection Sort)

선택 정렬(Selection Sort)란?

• 현재 위치에 들어갈 값을 찾아 정렬합니다.
• 현재 위치의 크기에 따라 최소 선택 정렬, 최대 선택 정렬로 구분할 수 있습니다.
  최소 정렬은 오름차순, 최대 선택 정렬은 내림차순으로 정렬됩니다.

선택 정렬 동작 방식(최소 선택 정렬)

• 정렬하려는 값의 크기를 n이라고 합니다.

1. 가장 처음 값 부터 마지막 값까지의 값 중 가장 작은 값을 찾아서 첫번째 값과 가장 작은 값이 있던 값과 위치를 변경합니다.
2. 두번째 값 부터 마지막 값까지의 값 중 가장 작은 값을 찾아서 두번째 값과 가장 작은 값이 있던 값과 위치를 변경합니다.
3. 세번째 값 부터 마지막 값까지의 값 중 가장 작은 값을 찾아서 세번째 값과 가장 작은 값이 있던 값과 위치를 변경합니다.
   .
   .
   .
   n-1. n-1 번째 값 부터 마지막 값까지의 값 중 가장 작은 값을 찾아서 세번째 값과 가장 작은 값이 있던 값과 위치를 변경합니다.

ex) int[] arr = new int[]{1, 5, 30, 9, 7}을 최소 선택 정렬로 정렬합니다.

1. 첫번째 인덱스의 값을 찾습니다. 1,5,30,9,7중 가장 작은 값은 1이며 1의 위치가 첫번째 인덱스에 위치하므로 변경되지 않습니다.
   {1, 5, 30, 9, 7}
2. 두번째 인덱스의 값을 찾습니다. 첫번째 인덱스는 앞에서 비교했으므로 제외하고 5, 30, 9, 7 중 가장 작은 값인 5를 찾습니다. 두번째 인덱스에 5가 있으므로 변경되지 않습니다.
   {1, 5, 30, 9 ,7}
3. 세번째 인덱스의 값을 찾습니다. 30, 9, 7 값을 비교하여 가장 작은 값인 7을 찾아 세번째 인덱스의 기존 30과 위치를 바꿉니다.
   변경된 값은 다음과 같습니다. {1, 5, 7, 9, 30}
4. 네번째 인덱스의 값을 찾습니다. 9, 30 값을 비교하여 가장 작은 값인 9을 찾습니다. 네번째 위치에 9가 위치하므로 변경되지 않습니다.
   {1, 5, 7, 9 , 30}
5. 마지막 이전 인덱스까지 비교가 끝났으므로 최소 선택 정렬이 완료되었습니다.

Java 최소 선택 정렬 코드

@Test
    public void minSelectionTest(){
        int[] arr = new int[]{1, 10, 9, 5, 8, 3, 7};

        System.out.println("===== 최소 선택 정렬 이전 =====");
        for (int a : arr){
            System.out.print(a + " ");
        }
        System.out.println();

        minSelectionSort(arr);

        System.out.println("===== 최소 선택 정렬 이후 =====");
        for (int a : arr){
            System.out.print(a + " ");
        }
    }

    /**
     * 최소 선택 정렬 구현
     * @param arr 정렬되지 않은 배열
     */
    void minSelectionSort(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            // index를 비교 - 마지막에 비교한 값 중 가장 작은 값의 인덱스 위치와 비교 인덱스 위치를 교환해야 하기 때문에
            int minIndex = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[minIndex] > arr[j]) minIndex = j;
            }
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }

결과

===== 최소 선택 정렬 이전 =====
1 10 9 5 8 3 7 
===== 최소 선택 정렬 이후 =====
1 3 5 7 8 9 10 

이 정렬 알고리즘은 n-1개, n-2개 ... 1개를 비교 반복하므로 시간복잡도는 O(n^2)입니다.