선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

  알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 두 번째로 정리할 정렬 알고리즘은 선택 정렬입니다.

 

선택 정렬이란?

선택 정렬은 배열을 순차적으로 탐색하면서 최소값 찾아 맨 앞에 위치한 값과 교체하는 방식입니다.

 

동작 원리

1. 배열의 첫 번째 원소부터 시작하여 나머지 원소들 중에 가장 작은 원소를 찾아 첫 번째 원소와 교환합니다.
2. 두 번째 원소부터는 이미 정렬된 부분을 제외한 나머지 배열을 탐색하여 가장 작은 값을 찾아 두 번째 원소와 교환합니다.
3. 이 과정을 배열 끝까지 반복하면서 정렬이 완료됩니다.

예시

패스	테이블	최솟값
0	[9, 1, 6, 8, 4, 3, 2, 0]	0
1	[0, 1, 6, 8, 4, 3, 2, 9]	1
2	[0, 1, 6, 8, 4, 3, 2, 9]	2
3	[0, 1, 2, 8, 4, 3, 6, 9]	3
4	[0, 1, 2, 3, 4, 8, 6, 9]	4
5	[0, 1, 2, 3, 4, 8, 6, 9]	6
6	[0, 1, 2, 3, 4, 6, 8, 9]	8

 

특징

• 시간 복잡도 : 최악 시간 복잡도는 O(N^2)입니다. 선택 정렬은 배열의 크기가 커져도 성능은 크게 달라지지 않습니다.
• 공간 복잡도 : O(1)입니다. 추가적인 메모리 공간을 거의 사용하지 않으며, 원본 배열을 직접 수정합니다.

선택 정렬 구현

public class SelectionSort{
    public static void main(String[] args) {
        int[] arr = new int[] {9, 1, 6, 8, 4, 3, 2, 0};
        
        System.out.println("정렬 전 배열");
       	for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        
        // 배열을 반복하면서
        for(int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;    // 최소값의 인덱스를 i로 설정
            
             // i 다음 인덱스부터 끝까지 탐색하여 최소값을 찾음
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;    // 더 작은 값을 찾으면 그 인덱스를 갱신
                }
            }
            
            // 찾은 최소값과 i번째 원소를 교환
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        
        System.out.println("정렬 후 배열");
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }
}

 

결과 화면