선택정렬 Selection Sort

정의

오름차순으로 정렬하는 기초적인 알고리즘 중 하나

기법

무차별 대입 Brute Force

알고리즘 순서

1. 순회해서 최소값을 찾는다
2. 첫번째 값과 최소값을 스왑한다
3. 두번쨰 값부터 순회해서 최소값을 찾는다
4. 두번쨰 값과 최소값을 스왑한다
5. 마지막 직전까지 반복한다.

자바 코드

    public static int[] selectionSort(int[] input) {
        for (int i = 0; i < input.length-1; ++i) {
            for (int j = input.length - 1; j > i; --j) {
                if (input[j] < input[i]) {
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                }
            }
        }
        return input;
    }

평균 시간 복잡도 Avg. time complexity

$O(n^2)$

최악 시간 복잡도 Worst time complexity

$O(n^2)$

공간 복잡도 space complexity

$O(1)$

안정성 stability

no

계산법

순회 횟수

$n-1$

가장 많이 방문한 요소 수

$n-1$ (마지막 요소)

가장 적게 방문한 요소 수

$1$ (첫번째 요소)

평균적으로 방문한 요소 수

(가장 많이 방문한 요소 수+가장 적게 방문한 요소)/2 $= \frac{(n-1+1)}{2} = \frac{n}{2}$

다항식 시간

순회 횟수*평균적으로 방문한 요소 수 $=(n-1)\cdot \frac{n}{2}$

시간 복잡도

$O(다항식 시간)=O((n-1)\cdot \frac{n}{2})=O((\frac{n^2}{2}-\frac{n}{2}))=O(n^2)$