선택 정렬(SelectionSort)

선택 정렬

원소 한개 한개를 확인해서 정렬한다.

따라서 시간복잡도가 O(n^2)이 된다.

 

예를 들어

100, 25, 40, 30 ,10을 가지고 오름차순 정렬을 하면

1. 10, 100, 25, 40, 30

2. 10, 25, 100, 40, 30

3. 10, 25, 30, 100, 40

4. 10, 25, 30, 40, 100

이렇게 정렬된다.

 

위키에 있는 이미지를 보면

원소 한개 한개를 확인해서 정렬하는것을 알 수 있다.

 

코드 구현

import java.util.ArrayList;

public class SelectionSort {
    //시간복잡도(빅오표기법) = O(n^2)
    public static void main(String[] args){
        ArrayList<Integer> input = new ArrayList<>();
        for(int i = 10;i>0;i--){
            input.add(i);
        }
        System.out.println(selectionSort(input));

    }
    public static int smallest(ArrayList<Integer> n){
        int small = n.get(0);
        int smallIdx = 0;
        for(int i = 1;i< n.size();i++){
            if(n.get(i)<small){
                small=n.get(i);
                smallIdx=i;
            }
        }
        return smallIdx;
    }
    public static ArrayList<Integer> selectionSort(ArrayList<Integer> n){
        ArrayList<Integer> newArr = new ArrayList<>();
        int size = n.size();
        for(int i = 0;i<size;i++){
            int smallestIdx = smallest(n);
            newArr.add(n.get(smallestIdx));
            n.remove(smallestIdx);
        }
        return newArr;
    }
}

참고

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC