[Sort] Selection

 

- 주어진 데이터 중 최소값을 찾음

- 최소값을 맨 앞에 위치한 값과 교환

- 정렬된 데이터를 제외한 나머지 데이터를 같은 방법으로 정렬

- 시간복잡도 : O(n^2)

 

선택 정렬의 장점

- 데이터의 양이 적을 때 좋은 성능을 나타냄.

- 작은 값을 선택하기 위해서 비교는 여러번 수행되지만 교환횟수가 적다.

 

선택 정렬의 단점

- 100개 이상의 자료에 대해서는 속도가 급격히 떨어져 적절히 사용되기 힘들다.

 

 

package algorithm.sort;

public class Selection {


    public static void main(String[] args){

        int[] arr = {3,6,1,9,2,7,4,8,5,0, 14,23,98,45,76,34};

        selectionSort(arr);

        System.out.println("===========================");
        for(int item : arr){
            System.out.print(item);
            System.out.print("|");
        }
        System.out.println();
        System.out.println("===========================");


    }

    private static void selectionSort(int[] arr){

        int max = 0;
        int tmp = 0;

        for(int i = 0 ; i < arr.length ; i++){


            for(int j = 0 ; j < arr.length - i ; j++){

                if(arr[j] > arr[max]){
                    max = j;
                }

            }

            tmp = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = arr[max];
            arr[max] = tmp;

            max = 0;

        }

    }

}