기본적인 알고리즘 - selection sort

 selection sort

 

개념

- 배열중에 가장 큰 값을 찾고 맨 끝값과 바꾼다. 이제 맨 끝값은 생각하지 않아도 된다.

 

좀 더 쉽게 계획을 세우면

1. 가장 큰 값을 찾는다.

2. 맨 끝 값과 바꾼다.

3. 맨 끝 값을 제외하고 배열의 나머지 값들로 1,2번을 반복한다.

 

9	5	3	7	6
5	3	7	6	9
5	3	6	7	9
5	3	6	7	9
3	5	6	7	8

빨간색 - 가장 큰 값

노랑색 - 배열의 원소들을 비교할 때 생각하지 않아도 되는 부분

 

시간 복잡도를 생각해보자

 

배열의 원소가 n개일 경우

우선 모든 배열의 값들을 다 비교해야 하므로 n-1번 반복해야한다.

가장 큰 값을 찾아야 하는데 이는 위의 n을 기준으로 달라진다.

따라서 

시간복잡도 T(n) = (n-1) + (n-2) + (n-3) + ..... + 2 + 1 = O(n^2)이다 

 

코드

package sort;
import java.util.Arrays;

public class selection_sort {
    public static void main(String[] args) {
        int[] base = {9,5,3,7,6};
        int max = base[0];
        int index=0;
        for(int i = base.length-1; i>0;i--){
            for(int j = 0;j<=i;j++){
                if(max <= base[j]){
                    index = j;
                    max = base[j];
                }
            }
            base[index] = base[i];
            base[i] = max;
            max = base[0];
        }
        System.out.println(Arrays.toString(base));
    }
}