[java] 선택 정렬 알고리즘

14 Dec 2023

java

이번 포스트에서는 선택 정렬(Selection Sort) 알고리즘에 대해 알아보겠습니다. 선택 정렬은 매우 간단하지만 이해하기 쉽고 구현하기 쉬운 정렬 알고리즘 중 하나입니다.

개요

선택 정렬 알고리즘은 다음과 같은 단계로 이루어집니다:

리스트에서 최솟값을 찾습니다.
그 값을 리스트의 맨 앞에 위치한 값과 교환합니다.
첫 번째 원소를 제외한 나머지 리스트를 같은 방법으로 정렬합니다.

이 알고리즘은 연산 횟수가 $O(n^2)$ 으로 비효율적이지만, 작은 규모의 데이터나 정렬되어 있는 상태에서의 정렬에는 적합합니다.

예제 코드

아래는 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

결론

선택 정렬은 간단한 알고리즘으로 이해하기 쉽고 구현하기도 쉽습니다. 하지만 대규모의 데이터에 대해 비효율적이므로 실제로 사용할 때는 고려해야 합니다.