선택 정렬(Selection Sort)은 그리디 알고리즘 중 하나로, 배열을 반복하면서 가장 작은 값을 찾아 맨 앞의 요소와 교환하는 방식으로 정렬하는 알고리즘입니다. 이 알고리즘은 비교적 간단하지만 큰 규모의 리스트를 정렬할 때 효율적이지 않습니다.

알고리즘 동작

1. 배열을 처음부터 끝까지 반복하면서 가장 작은 값을 찾습니다.
2. 찾은 가장 작은 값을 현재 위치의 값과 교환합니다.
3. 다음 위치에서 위의 과정을 반복합니다.
4. 배열이 정렬될 때까지 위의 과정을 반복합니다.

Java 코드 예시

다음은 Java로 구현된 선택 정렬 알고리즘의 간단한 예시 코드입니다.

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

이 코드에서 selectionSort 메서드는 선택 정렬을 수행합니다. 알고리즘의 원리를 코드에서 찾아보실 수 있습니다.

마치며

선택 정렬 알고리즘은 간단하지만 큰 규모의 배열을 정렬하는 데 비효율적이며, 평균 시간 복잡도가 O(n^2)입니다. 따라서, 더 효율적으로 정렬을 수행할 수 있는 다른 정렬 알고리즘을 사용하는 것이 좋습니다.

참고 문헌:

• Selection Sort Algorithm
• Selection Sort - Wikipedia