삽입 정렬(Insertion Sort)

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식

 

시간 복잡도 : O(N^2)

 

선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것

 

📌 정렬 과정

 

1. 현재 index에 있는 데이터 값을 선택
2. 현재 선택한 데이터가 정렬된 데이터 범위에서 삽입될 위치를 탐색
   • 처음 자신보다 작은 값이 나올 때까지(오름차순)
   • 처음 자신보다 큰 값이 나올 때까지(내림차순)
3. 삽입 위치부터 index 위치까지 shift 연산(우측 이동)을 수행
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산을 수행
5. 마지막 index까지, 즉 선택할 데이터가 없을 때까지 반복

 

 

📌 알고리즘

 

import java.io.IOException;

public class Main {

    public static void main(String[] args) throws IOException {
        int N = readInt();
        int[] A = new int[N];
        StringBuilder ans = new StringBuilder();

        for (int i = 0; i < N; i++) {
            A[i] = readInt();
        }

        for (int i = 1; i < N; i++) {
            int insertion_point = i;
            int insertion_value = A[i];
            for (int j = i - 1; j >= 0; j--) {
                if (A[j] < A[i]) {
                    insertion_point = j + 1;
                    break;
                }
                if (j == 0) insertion_point = 0;
            }
            for (int j = i; j > insertion_point; j--) {
                A[j] = A[j - 1];
            }
            A[insertion_point] = insertion_value;
        }

        for (int i = 0; i < N; i++) {
            ans.append(A[i]).append(" ");
        }

        System.out.println(ans);
    }

    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

Reference: