[Sorting] 삽입 정렬(selection sort)(BOJ 1427번)

1. 삽입 정렬의 정의 2. 삽입 정렬의 과정 3. BOJ 11399: ATM

1. 삽입 정렬의 정의

• 데이터를 하나씩 적절한 위치에 삽입시키는 정렬
• 시간 복잡도 O(n²)로 느린 편이지만 구현이 쉽다

 

2. 삽입 정렬의 과정

① 정렬 범위 내에서 최솟값(최댓값)을 찾는다

② 맨앞의 데이터와 swap한다

③ 정렬 범위를 축소한다

④ 남은 정렬 범위가 없을 때까지 ①~③을 반복한다

 

 

3. BOJ 11399: ATM

public class B11399_ATM {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        int[] nArr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }
        // input

        for(int i=1; i<N; i++){
            int idx = i;
            int value = arr[i];
            for(int j=i-1; j>=0; j--){
                if(arr[j] < arr[i]){
                    idx = j+1;
                    break;
                }
                if(j==0)
                    idx=0;
            }

            for(int j=i; j>idx; j--)
                arr[j] = arr[j-1];
            arr[idx] = value;
        }

        nArr[0] = arr[0];
        for(int i=1; i<N; i++)
            nArr[i] = nArr[i-1] + arr[i];

        int sum=0;
        for(int i=0; i<N; i++)
            sum = sum + nArr[i];
        // operation

        System.out.println(sum);
        // output
    }
}​