정렬 - Selection Sort

선택 정렬(Selection Sort)는 배열의 원소 중에서 원하는 위치에 놓을 데이터를 찾아 선택하는 것

 

어떤 배열을 오름차순으로 정렬하고 싶다고 가정하고 설명하도록 한다.

int[] array = {5, 9, 1, 7, 2}; 인 배열 array가 있다고 하자.

정렬을 할 때마다 배열의 맨 앞부터의 위치들에 최솟값들이 하나씩 이동하게 되므로

이미 최솟값을 이동시킨 위치는 고려하지 않고, 그 다음 위치들 중에서 최솟값을 찾는다.

 

즉, 전체적인 과정을 설명하면,

 

1. 배열의 각 원소 중에서 최솟값을 찾고, 이를 array[0]과 자리를 바꾼다. (swap)

2. array[0]을 제외한 나머지 원소들 중에서 최솟값을 찾아 array[1]과 자리를 바꾼다.

3. array[2], array[3]....도 위의 방법대로 반복한다.

 

이때, (배열의 길이 - 1)만큼만 최솟값을 찾는 cycle을 진행하면 되는데, 

위의 예시에서 총 5개의 데이터 중에서 4개의 데이터를 정렬했다는 것은 이미 마지막 데이터는 정렬이 되었다는 의미이기 때문이다. (최솟값을 찾고 나머지 값들과 비교하여 정렬했으므로 2개씩 비교가 되었기 때문) 

 

이를 코드를 작성하여 비교해보자.

import java.util.Arrays;
 
public class Selection_Sort {
    public static void main(String[] args) {
        // 선택정렬을 통해 오름차순으로 정렬
        int[] array = { 5, 9, 1, 7, 2 };
        // 최솟값을 갖는 index를 찾아 그 index 자리의 값과 array[i]값을 바꿔준다.
        for (int i = 0; i < array.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIdx] > array[j]) {
                    minIdx = j;
                }
            }
            int tmp = array[i];
            array[i] = array[minIdx];
            array[minIdx] = tmp;
        
        }
        System.out.println(Arrays.toString(array));
    }
}
 

내림차순도 같은 논의로 진행해보면, (부등호의 방향만 반대)

import java.util.Arrays;
 
public class Selection_Sort {
    public static void main(String[] args) {
        // 선택정렬을 통해 내림차순으로 정렬
        int[] array = { 5, 9, 1, 7, 2 };
        // 최댓값을 갖는 index를 찾아 그 index 자리의 값과 array[i]값을 바꿔준다.
        for (int i = 0; i < array.length - 1; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[maxIdx] < array[j]) {
                    maxIdx = j;
                }
            }
            int tmp = array[i];
            array[i] = array[maxIdx];
            array[maxIdx] = tmp;
        
        }
        System.out.println(Arrays.toString(array));
    }
}
 

그 결과, {9, 7, 5, 2, 1}로 내림차순 정렬이 됨을 확인할 수 있다.