[Algorithm] 자바[Java] - 선택 정렬(Selection Sort) 알고리즘

선택 정렬[Selection Sort]

선택 정렬은 정렬 알고리즘 중에서 이해하기 쉽고 기본적인 알고리즘 중 하나입니다. 선택 정렬은 배열에서 가장 작은(또는 가장 큰) 원소를 찾아서 정렬되지 않은 부분의 첫 번째 원소와 교환하는 과정을 반복하는 방식으로 동작합니다.

가장 작거나 큰 원소를 선택하고 그 위치를 바꿔주기 때문에 선택 정렬이라는 이름을 사용합니다.

선택 정렬의 특징

선택 정렬은 비교 정렬에 속하며, 제자리 정렬(in-place sort)입니다. 즉, 추가적인 메모리 공간을 거의 사용하지 않고, 주어진 배열 안에서 원소를 교환하여 정렬을 수행합니다. 선택 정렬은 대규모 데이터 세트에는 비효율적일 수 있지만, 알고리즘의 동작 원리를 이해하는 데 매우 유용한 도구입니다.

• 선택 정렬의 과정
  • 이 과정은 정렬되지 않은 부분을 점점 줄여가며 수행됩니다.
  • 배열의 두 번째 요소부터 시작하여 현재 범위 내에서 가장 작은(혹은 가장 큰) 원소를 찾습니다.
  • 해당 원소를 현재 범위의 첫 번째 원소와 교환합니다.
  • 다음 반복에서는 범위를 좁혀가며, 이 과정을 배열이 정렬될 때까지 계속합니다.

• 장점
  
  • 구현이 매우 간단하고 직관적입니다.
  • 데이터의 이동 횟수가 적습니다. 한 번의 반복(iteration)에서 최대 한 번의 교환(swap)만 발생합니다.
• 단점
  • 시간 복잡도 : 최선, 평균, 최악의 경우 모두 O(n²)로, 데이터 양이 많을수록 매우 비효율적입니다.
  • 정렬된 상태에서도 모든 비교를 수행하므로, 데이터의 초기 상태에 관계없이 동일한 시간이 소요됩니다.

정렬 방법 및 구현

아래는 자바 코드로 구현한 선택 정렬의 예시입니다.

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 7, 1, 3, 2, 9, 6, 8};
        selectionSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    // 선택 정렬 알고리즘
    private 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;
        }
    }
}

// 1, 2, 3, 4, 5, 6, 7, 8, 9

선택 정렬의 시간 복잡도와 공간 복잡도

• 시간 복잡도 : 선택 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n²)입니다. 이는 정렬된 데이터, 반대로 정렬된 데이터 모두에서 동일한 시간 복잡도를 가진다는 것을 의미합니다.
• 공간 복잡도 : 선택 정렬은 제자리 정렬로, 추가적인 메모리 사용이 거의 없으므로 공간 복잡도는 O(1)입니다.

REF.

https://www.geeksforgeeks.org/java-program-for-selection-sort/

Java Program for Selection Sort