삽입정렬이란?

김혁준·2024년 10월 8일

코테스터디

목록 보기

3/6

삽입정렬

삽입정렬이란?

삽입 정렬은 특정 데이터를 리스트의 앞에서부터 이미 정렬된 서브 리스트의 값들과 비교하여 자신의 위치에 삽입하는 방식. 서브 리스트는 이미 정렬이 되어있기 때문에 서브 리스트 안에서도 자신이 삽입이 되어야 할 위치가 정해져 있다. 그 위치에 데이터를 삽입하는 것이 바로 삽입 정렬이다.
서브 리스트는 처음에는 0번 인덱스로 정하고 순회할때마다 한개씩 늘어난다.

구현 방법

시작 지점이 있으면 그 앞의 정렬된 부분집합인 S들의 요소들과 비교하게 되는데
만약 S의 요소가 크다면 그 요소의 위치를 +1해주는걸 반복하다가, S의 요소가 작을 때 [현재 비교한 위치 +1]번방에 삽입하게 된다.
배열 [67, 10, 32, 5, 16] 이 있을 때의 과정은 아래 그림처럼 동작하게 된다.

삽입 정렬 - 그림 설명

1회전

첫 시작으로 2번째 원소인 10을 기준으로 앞의 원소들과 비교한다.

10과 67을 비교하여 10이 작으므로 67의 위치는 +1해주고, 그 자리에 삽입한다.

2회전

3번째 원소인 32를 기준으로 비교한다.

첫번째로 67과 비교하여 더 작으므로 67의 위치를 +1 해주고, 그 다음 원소인 10과 비교한다.

10보다는 크므로 그 앞에 값을 삽입한다.

3회전

4번째 원소인 5를 기준으로 비교한다.

첫번째로 67과 비교하여 더 작으므로 67의 위치를 +1 해주고, 그 다음 원소인 32와 비교한다.

32보다 작으므로 32의 위치를 +1 해주고, 그 다음 원소인 10과 비교한다.

10보다 작으므로 10의 위치를 +1 해주고, 제일 앞에 값을 넣는다.

4회전

5번째 원소인 16을 기준으로 비교한다.

첫번째로 67과 비교하여 더 작으므로 67의 위치를 +1 해주고, 그 다음 원소인 32와 비교한다.

32보다 작으므로 32의 위치를 +1 해주고, 그 다음 원소인 10과 비교한다.

10보다 크므로 그 앞에 값을 넣는다.
정렬이 안된 부분집합 U가 없으므로(공집합이므로) 전부 정렬이 됐다.

코드

public static void insertionSort(int[] a, int size) {
        for (int i = 1; i < size ; i++) {
            
            // 타겟 넘버
            int target = a[i];
            
            int j = i -1;

            // 타겟이 이전 원소보다 크기 전까지 반복
            while (j >= 0 && target < a[j]) {
                a[j+1] = a[j];
                j--;
            }
            
            // while문을 탈출하는 경우 타겟은 j번째 원소 뒤에 와야 하므로 타겟은 j+1에 위치하게 된다.
            a[j+1] = target;
        }
    }

문제

백준 2751
https://www.acmicpc.net/problem/2751

알고리즘 [접근 방법]

삽입 정렬은 시간복잡도가 O(N^2)이므로 시간이 초과된다. 병합정렬, 힙 정렬, 팀 정렬들을 써야한다.
하지만 지금은 삽입정렬을 공부하는게 목적이기 때문에 삽입정렬을 사용해보겠다. 물론 아래 코드는 실제로 백준에 제출하면 시간초과가 나온다.

풀이방법

삽입정렬을 사용한다. 입력받은 값을 배열에 초기화하고 반복문을 돌린다.

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

두번째 원소를 키로 잡고 j를 i-1로 잡아서 j가 0보다 클때까지 j를 1씩 빼주면서 원소들을 한칸 뒤로 밀어낸다. 그리고 어느 한 배열이 키보다 작으면 그 배열의 한칸 뒤에 키값을 넣는다.

풀이

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = num;
        }

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

        for (int i = 0; i < N; i++) {
            System.out.println(arr[i]);
        }
    }
}