선택 정렬(Selection Sort) 알고리즘 이해하기

정렬 알고리즘 중에서 간단한 선택 정렬(Selection Sort) 알고리즘에 대해 이야기하려고 합니다. 이 글에서는 선택 정렬의 원리와 Java 코드 예제를 통해 알고리즘을 구현하는 방법을 알아보겠습니다.

선택 정렬(Selection Sort)이란?
선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 해당 위치의 값과 교환하는 과정을 반복하여 전체 배열을 정렬하는 알고리즘입니다.

선택 정렬의 원리
선택 정렬의 기본 원리는 다음과 같습니다:

1. 정렬되지 않은 부분에서 최소값(또는 최대값)을 찾습니다.
2. 찾은 최소값을 정렬되지 않은 부분의 첫 번째 원소와 교환합니다.
3. 전체 리스트가 정렬될 때까지 위 과정을 반복합니다.

 

Java로 선택 정렬 구현하기

public class SelectionSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        selectionSort(arr);

        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

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

위 코드에서 selectionSort 메소드는 선택 정렬 알고리즘을 구현한 것입니다. 이 메소드는 정수 배열을 입력으로 받아 배열을 오름차순으로 정렬합니다. 이를 위해 두 개의 중첩된 반복문을 사용하여, 배열의 최소값을 찾고 해당 위치의 원소와 교환합니다.

이상으로 Java에서 선택 정렬 알고리즘을 구현하는 방법에 대해 알아보았습니다. 선택 정렬은 구현이 간단하고 이해하기 쉬운 정렬 알고리즘이지만, 최악의 경우 시간 복잡도가 O(n^2)로 비효율적입니다. 따라서 대용량 데이터를 다룰 때는 다른 정렬 알고리즘을 사용하는 것이 좋습니다.