[알고리즘] 선택정렬(Selection Sort)

배열에서 아직 정렬되지 않은 부분에서 가장 큰 값 을 하나 선택해 그 값을 가장 뒤(last)로 보내는 과정을 반복하는 정렬 알고리즘이다. (최솟값을 기준으로 정렬하는 것도 가능)

 

추가적인 메모리를 요구하지 않는 정렬 방법으로 In-place 정렬 알고리즘이라 한다. 반대는 Not In-place

대표적인 In-place 정렬 알고리즘 : 선택 정렬, 삽입 정렬, 버블 정렬, 힙 정렬, 퀵 정렬

Not In-place 정렬 알고리즘: 병합 정렬, 기수 정렬, 계수 정렬 등

 

 

처음 last = N - 1이고 단계를 거듭할 수록 N - 2, N - 3 .. 으로 줄어든다. 0 ~ last 구간에서 가장 큰 값을 찾아, 그 값을 맨 뒤(last)로 보내는 방식이다.

선택 정렬은 빠른 정렬 알고리즘은 아니지만, 정렬의 기본 원리를 이해하는 데 있어서는 가장 좋은 출발점이 되는 알고리즘이다.

 

 

시간 복잡도

• 최선, 평균, 최악의 경우 모두 O(N²) 

최선	평균	최악
O(N²)	O(N²)	O(N²)

장점

1. 구현이 단순하다
2. 교환 횟수가 적다

• 최대 교환 횟수는 N - 1번

3. 동작 과정이 명확하다

• 디버깅 시 적합

단점

매우 느리다

• 시간 복잡도가 O(N²) 라 데이터 개수가 커질수록 성능이 떨어진다.

 

예시코드

static void selectionSort(int[] nums, int last) {

        if (last <= 0) {
            return;
        }

        int max = nums[0];
        int maxIdx = 0;
        for (int i = 0; i <= last; i++) {
            if (max < nums[i]) {
                max = nums[i];
                maxIdx = i;
            }
        }

        if (maxIdx != last) {
            int tmp = nums[maxIdx];
            nums[maxIdx] = nums[last];
            nums[last] = tmp;
        }

        selectionSort(nums, last - 1);

    }

 

 

 

기초 백준 문제

https://www.acmicpc.net/problem/23881