초보 자바 프로그래밍(19) - 선택정렬 (Selection Sort)

선택 정렬 대표 이미지

🔖 INDEX

 

 

선택 정렬(Selection Sort)은 간단한 비교 기반 정렬 알고리즘 중 하나로, 배열에서 최솟값(또는 최댓값)을 찾아 정렬되지 않은 부분의 첫 번째 원소와 교환하는 방식으로 정렬을 수행합니다. 선택 정렬은 구현이 쉽고 간단하지만, 효율성이 떨어져 큰 데이터 셋에는 적합하지 않습니다.

 

선택 정렬의 작동 원리

선택 정렬의 작동 원리는 다음과 같습니다: ​

1. 배열에서 최솟값을 찾습니다. 이 원소가 정렬되지 않은 부분의 첫 번째 원소입니다.
2. 최솟값을 정렬되지 않은 부분의 첫 번째 원소와 교환합니다. 이로써 최솟값이 정렬된 위치에 있게 됩니다.
3. 정렬된 원소를 제외한 나머지 부분에서 다시 최솟값을 찾고, 이를 정렬되지 않은 부분의 첫 번째 원소와 교환합니다.
4. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

 

선택 정렬의 특징

선택 정렬의 특징은 다음과 같습니다: ​

1. 불안정 정렬(Unstable Sort): 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 변경될 수 있습니다.
2. 제자리 정렬(In-place Sort): 추가적인 메모리를 사용하지 않고 입력 배열 안에서 정렬이 이루어집니다.
3. 시간 복잡도(Time Complexity): 최선, 평균, 최악의 경우 모두 O(n^2)의 시간 복잡도를 가집니다. 이로 인해 큰 데이터 셋에는 적합하지 않습니다. ​

선택 정렬은 작은 데이터 셋이나 간단한 프로젝트에 적합한 정렬 알고리즘이지만, 성능이 중요한 상황에서는 더 효율적인 알고리즘을 사용하는 것이 좋습니다. 예를 들어 퀵 정렬, 병합 정렬, 힙 정렬 등이 더 큰 데이터 셋에서 더 좋은 성능을 보입니다.

 

 

선택 정렬의 구현 예제

선택 정렬은 다음과 같이 구현할 수 있습니다.

// SelectionSort 클래스 선언
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, 34, 25, 12, 22, 11, 90};
        // 정렬 전 배열 출력
        System.out.println("Unsorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }

        // 선택 정렬 실행
        selectionSort(arr);

        // 정렬 후 배열 출력
        System.out.println("\nSorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}