[정렬] 선택정렬 (Selection Sort) - Java

1. 개요

선택정렬이란, 배열의 맨 앞 요소를 선택한 후 그 다음 요소부터 가장 작은 값을 찾아 맨 앞 요소와 비교 후 swap 하는 형식의 정렬 알고리즘이다. (오름차순 기준)

 

 

2. 시간복잡도

모든 배열의 요소를 첫 요소로 잡고 (N), 그 다음 요소부터 끝까지 최소값을 찾아야하므로 (N) 시간복잡도는 O(N^2)이다.

 

 

3. 핵심이론

- 배열의 크기를 5로 가정

5

1

3

2

4

 

- 맨 앞 요소를 선택 후 그 다음 요소부터 최소값을 찾은 후  비교하여 서로 swap 한다.

5 (맨 앞 요소 선택)

1 (최소값)

3

2

4

1

5

3

2

4

 

- 위 과정을 반복한다.

1

5 (맨 앞 요소 선택)

3

2 (최소값)

4

1

2

3

5

4

 

1

2

3 (맨 앞 요소 선택)

5

4 (최소값)

1

2

3

5

4

 

1

2

3

5 (맨 앞 요소 선택)

4 (최소값)

1

2

3

4

5

 

- 정렬 완료

 

 

4. 예시 코드

public class Main {
    public static void selectionSort(int[] arr){
        // 맨 앞 요소 설정은 배열의 가장 끝 바로 앞까지만 설정
        for(int i = 0; i < arr.length - 1; i++){
            // 현재 위치를 최소값으로 가정
            int minIdx = i;
            // 현재 위치의 바로 다음 요소부터 배열의 끝까지 순회하며 최소값을 찾는다.
            for(int j = i + 1; j < arr.length; j++){
                // 현재 위치의 요소보다 더 작은 값이 있다면
                if(arr[minIdx] > arr[j]){
                    // 그 인덱스를 최소값의 인덱스로 설정한다.
                    minIdx = j;
                }
            }
            // 순회 종료 후 swap 진행
            swap(arr, i, minIdx);
        }
    }

    public static void swap(int[] arr, int t1, int t2){
        int temp = arr[t1];
        arr[t1] = arr[t2];
        arr[t2] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 3, 2, 4};

        selectionSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

출력 결과 : 1 2 3 4 5