[정렬] Selection Sort

선택 정렬의 개념

선택 정렬이란?

넣을 위치는 이미 정해져 있고, 그 위치에 어떠한 데이터를 넣을지 선택하는 알고리즘이다.

동작 방식

1. 리스트 길이(n)의 -1 만큼 반복한다. (앞에서부터 위치를 정하게 되면 마지막 값은 자동으로 위치가 정해진다)

    1-2. 선택된 최솟값과 최솟값이 들어갈 위치의 값과 교체한다.

    1-1. 값이 들어갈 위치부터 마지막 값까지 최솟값을 찾는다.

    void sort() {
        int min;
        // 1. 값이 들어갈 위치를 선택하는 반복문
        for(int i=0; i<numbers.length-1; i++) {
            min = i;
            // 1-1. 값이 들어갈 위치 뒤에 있는 데이터들 중에 최솟값을 찾는다
            for(int j=i; j<numbers.length; j++) {
                if(numbers[j] < numbers[min]) min = j;
            }
            // 1-2. Swap
            SWAP(i,min);
        }
    }

    void SWAP(int n1, int n2) {
        int temp = numbers[n1];
        numbers[n1] = numbers[n2];
        numbers[n2] = temp;
    }

 

선택 정렬의 장단점

장점 

1. 데이터의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.

 

단점

1. 어떤 상황이든 O(N^2)의 시간 복잡도를 갖기 때문에 훌륭한 성능을 보여주긴 힘듬
2. stable sort 방법이기 아니기 때문에, 두 개의 키값을 가지고 정렬을 시도할 수 없음

시간 복잡도

1. 리스트 길이(n)의 -1 만큼 반복한다. (값이 들어갈 위치는 마지막 값을 제외한 n-1개)

    1-1. 값이 들어갈 위치부터 마지막 값까지 최솟값을 찾는다. → n-1, n-2, n-3 ..... 1

    1-2. 선택된 최솟값과 최소값이 들어갈 위치의 값과 교체한다.

→  1 + 2 + 3 + ...... + n-1 = n(n-1)/2

    O(n^2)이다.

    어떠한 상황이든 최소값을 찾기 위해 1-1. 를 수행하기 때문에 최선, 평균, 최악의 경우 모두 O(n^2)이다.