[코테 알고리즘] 삽입 (Insert) 정렬

삽입(Insert) 정렬

---

각 숫자를 적절한 위치에 삽입해보자
적절한 위치의 왼쪽원소들은 이미 정렬되어있다고 가정
자신이 왼쪽원소보다 크다면 그 곳이 적절한 위치이다.(오름차순일 때)

🕑 시간복잡도: O(N^2)
[ 비교연산횟수: N-1 + N-2 + N-3 + ... + 1 = (N^2)/2번 ]
[ 도중에 왼쪽원소보다 크면 멈출 수 있어서 버블정렬보다 빠르다 ]

삽입(Insert) 정렬 코드 구현

---

1. 앞쪽부터 범위를 늘려간다.
2. 범위내 뒤에서부터 왼쪽보다 큰 지를 검사한다.
- 크면 멈춘다.
- 작으면 swap

<백준 알고리즘, 11399번>

🎯 인출시간이 짧은 사람이 먼저 인출할 수 있도록 하면 기다리는 시간이 짧아진다.

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] A = new int[N];
        int[] S = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }

        for(int i = 0; i < N-1; i++) {
            int j = i;
            while(j >= 0 && A[j+1] < A[j]) {
                int temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
                j--;
            }
        }

        S[0] = A[0];
        for(int i = 1; i < N; i++) {
            S[i] = S[i-1] + A[i];
        }
        int sum = 0;
        for(int i = 0; i < N; i++) {
            sum += S[i];
        }
        System.out.println(sum);
    }
}