자바 코딩테스트 강좌, 선택 정렬

1. 선택 정렬(Selection Sort)란?

선택 정렬은 정렬 알고리즘 중 하나로, 주어진 배열에서 가장 작은(혹은 가장 큰) 원소를 선택하여
정렬을 수행하는 방식입니다. 이 알고리즘은 배열의 길이가 n일 때, n-1번의 비교 연산을 통해
정렬이 완료되기 때문에 O(n^2)의 시간복잡도를 가집니다.

선택 정렬의 주요 특징은 단순하고 직관적이며 메모리 사용이 효율적이라는 점입니다.
그러나 대량의 데이터에서 성능이 떨어지기 때문에 일반적으로는 복잡한 데이터에서
다른 정렬 알고리즘이 더욱 효율적입니다.

2. 선택 정렬의 방법론

선택 정렬은 다음 단계로 이루어져 있습니다:

1. 배열에서 최솟값을 찾는다.
2. 찾은 최솟값과 현재 위치의 원소를 교환한다.
3. 위 과정을 배열의 끝까지 반복한다.

이 과정을 좀 더 시각적으로 이해하기 위해, 5개의 숫자로 이루어진 배열을 예로 들어보겠습니다.
[64, 25, 12, 22, 11]라는 배열이 있을 때, 선택 정렬은 다음과 같이 동작합니다.

2.1. 예제: 배열 정렬 과정

초기 배열: [64, 25, 12, 22, 11]

1. 첫 번째 원소(64)와 나머지 원소 중 최솟값(11)을 교환:
   [11, 25, 12, 22, 64]
2. 두 번째 원소(25)와 나머지 원소 중 최솟값(12)을 교환:
   [11, 12, 25, 22, 64]
3. 세 번째 원소(25)와 나머지 원소 중 최솟값(22)을 교환:
   [11, 12, 22, 25, 64]
4. 네 번째 원소(25)와 마지막 원소(64)를 교환할 필요없이 두 원소는 이미 정렬된 상태이므로:
   [11, 12, 22, 25, 64]

최종적으로 정렬된 배열은 [11, 12, 22, 25, 64]입니다. 이처럼 선택 정렬은 매우 직관적이고
간단한 방법으로 정렬을 수행할 수 있습니다.

3. 자바로 구현하기

이제 자바 언어로 선택 정렬을 구현해보겠습니다.

                
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("정렬된 배열: " + java.util.Arrays.toString(arr));
    }

    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;
                }
            }

            // Swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}
                
            

위의 Java 코드는 선택 정렬을 구현한 예입니다. selectionSort 메서드는 주어진 배열의 길이를
확인한 후, 각 원소에 대해 다음 단계로 진행합니다. 첫 번째 중첩 루프는 현재 원소 이후의 원소들을 비교하여
최솟값의 인덱스를 결정하고, 그 후 두 원소를 교환합니다.

4. 선택 정렬의 시간복잡도

선택 정렬의 시간복잡도는 O(n^2)입니다. 이는 최악의 경우와 최선의 경우 모두 동일합니다. 왜냐하면
모든 원소를 한 번씩 비교해야 하기 때문입니다. 비록 선택 정렬이 탐색과 스왑만으로 수행되므로
추가적인 메모리 낭비는 없지만, 큰 데이터셋에서는 비효율적임을 알 수 있습니다.

선택 정렬의 공간 복잡도는 O(1)입니다. 이는 추가적인 메모리 공간을 사용하지 않고, 주어진
배열 내에서만 정렬 작업이 이루어지기 때문입니다. 이 점은 선택 정렬의 큰 장점 중 하나입니다.

5. 선택 정렬 사용 예시 및 장단점

5.1. 장점

• 구현이 간단하고 이해하기 쉽다.
• 추가적인 메모리 사용 없이 배열 내에서 정렬이 이루어진다.
• 데이터가 거의 정렬된 상태일 경우 효율적으로 동작할 수 있다.

5.2. 단점

• 대량의 데이터를 정렬할 경우 비효율적이다.
• 최악의 경우와 최선의 경우 시간복잡도가 동일하다.
• 일반적으로 다른 정렬 알고리즘에 비해 성능이 떨어진다.

6. 선택 정렬의 응용

선택 정렬은 단순성과 효율성 덕분에 교육적 목적으로 많이 사용됩니다.
알고리즘과 데이터 구조의 기본을 배우기 위한 입문 과정에서는 선택 정렬이
자주 활용됩니다. 또한 제한된 메모리 환경에서 스왑을 통한 정렬이 필요한 경우에
사용될 수 있습니다.

예를 들어, 실시간 데이터 스트림에서 간단한 정렬 로직이 필요할 때
선택 정렬을 사용할 수 있습니다. 하지만 대량의 데이터 처리에는
더 빠른 정렬 알고리즘을 사용하는 것이 더 적합합니다.

7. 마무리 및 참고 자료

선택 정렬은 가장 직관적인 정렬 알고리즘 중 하나로, 알고리즘을 배우는 데 매우 유용합니다.
그러나 실제 환경에서는 더 효율적인 알고리즘을 사용하는 것이 좋습니다.
이 강좌를 통해 선택 정렬의 개념과 구현 방법을 이해하고, 자바 코딩 테스트를 준비하는 데 도움이 되기를 바랍니다.

참고 자료:

• Geeks for Geeks – Selection Sort
• Wikipedia – Selection Sort
• TutorialsPoint – Selection Sort