[Algorithms] 선택 정렬

선택 정렬(Selection Sort)은 간단한 정렬 알고리즘 중 하나로, 주어진 리스트에서 매번 가장 작은(혹은 가장 큰) 요소를 찾아 그것을 리스트의 맨 앞(혹은 맨 뒤)으로 옮기는 작업을 반복하는 방식입니다. 시간 복잡도는 O(n2)로, 정렬해야 할 항목이 많을 경우 비효율적이지만, 구현이 매우 간단합니다.

 

선택 정렬의 동작 과정입니다.

1. 주어진 리스트에서 가장 작은 값을 찾아 첫 번째 위치에 있는 값과 교환합니다.
2. 두 번째 위치부터 끝까지 중에서 다시 가장 작은 값을 찾아 두 번째 위치에 있는 값과 교환합니다.
3. 이를 마지막 요소까지 반복합니다.

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 배열에서 n개의 원소에 대해 반복
        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;
                }
            }

            // 현재 위치와 최소값의 위치가 다를 경우 교환
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        
        System.out.println("정렬 전 배열:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

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

        System.out.println("정렬 후 배열:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}


// 정렬 전 배열:
// 64 25 12 22 11 
// 정렬 후 배열:
// 11 12 22 25 64

 

끝.