[알고리즘] 삽입 정렬(Insertion Sort)이란 ?

📁삽입 정렬

정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬하는 방식으로 시간 복잡도가 O(n²)으로 효율적이지 않아 코딩 테스트에서는 많이 사용되지는 않는다.

1️⃣ 삽입 정렬의 과정

1. 선택 인덱스(=index 1)의 데이터를 선택한다.
2. 선택 인덱스의 데이터보다 인덱스 값이 작은 위치에 선택 데이터보다 큰 값이 존재하지 않을 때까지 위치를 변경한다.
3. 마지막 변경 인덱스와 선택 인덱스와 위치 변경

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[] {5, 4, 1, 3, 2};

        arr = insertSort(arr);

        System.out.println(Arrays.toString(arr));
    }
	
    public static int[] insertSort(int[] arr) {
				// 삽입 정렬은 index 1부터 시작하기 때문에 1부터 배열 크기만큼 정렬한다.
        for(int i = 1; i < arr.length; i++) {
		        // key = 선택 데이터
            int key = arr[i];
            int j = i - 1;
						// 4를 저장해두고 5 4 1 3 2 -> 5 5 1 3 2 -> 4 5 1 3 2
						// 1을 저장해두고 4 5 1 3 2 -> 4 5 5 3 2 -> 4 1 5 3 2 -> 1 4 5 3 2
						// 1 4 3 5 2 -> 1 3 4 5 2
						// 1 3 4 2 5 -> 1 3 2 4 5 -> 1 2 3 4 5
						// 선택 데이터보다 앞 인덱스에 큰 값이 존재하지 않을 때까지 위치 변경
            while(j >= 0 && arr[j] > key) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    }
}

2️⃣ 삽입 정렬 정리

1. 삽입 정렬은 안정 정렬(Stable Sort)이다.

   • 같은 값을 가지는 원소의 순서가 정렬 전과 동일하게 유지된다.

2. 제자리 정렬(In-Place Sort)이다.

   • 입력 배열 내에서 정렬이 수행되므로 별도의 추가 메모리가 필요하지 않는다.

3. 데이터가 거의 정렬되어 있을 때는 효율적이다.

   • 입력 배열이 이미 정렬되어 있는 경우, 삽입 정렬은 더 빠르게 수행되지만 역순으로 정렬되어 있을 경우, 최악의 시간복잡도 O(n²)를 가진다.

3️⃣ 정렬 알고리즘 시간복잡도 비교

4️⃣ 삽입 정렬 코딩테스트 예제

11399. ATM

📌 문제 탐색하기

🌝 입력

1. 수 N이 주어진다. (1 <= N <= 1,000)
2. 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 <= P <= 1,000)

🌑 출력

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

🕔 시간제한

1초

🚨 접근

삽입 정렬을 활용해 정렬해보자.

• Java에서 제공하는 정렬을 하면 되지만 삽입 정렬 공부를 위해 삽입 정렬을 통해 정렬을 해보자.

🙆‍♂️ 가능한 시간복잡도

시간 초과는 생각할 필요 없다.

• N이 1,000보다 작기때문에 이중으로 반복을 수행해도 1,000,000이 나오기 때문에 시간초과에 대해 생각할 필요는 없다.

📌 문제 풀이

1. 하나의 ATM에 여러 사람이 돈을 입금할 때 여러 사람이 수행하는 데 걸리는 시간의 합의 최솟값은 오름차순으로 정렬된 상태여야 최솟값이 나온다.
2. 오름차순으로 정렬한 뒤 반복문을 통해 시간의 합을 구해 출력한다.

📌 정답 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        insertSort(arr);
        
        int result = 0;

        // 인덱스 기준 (0 + 0, 1 + 0, 1, 2 + ... + 0, 1, 2, ..., n)을 수행하기 위한 이중 for문
        for(int i = 0; i < n; i++) {
            result += arr[i];

            for(int j = 0; j < i; j++) {
                result += arr[j];
            }
        }

        System.out.println(result);
    }

    static void insertSort(int[] arr) {

        for(int i = 1; i < arr.length; i++) {
            int data = arr[i];
            int j = i - 1;

            // arr[i] 값보다 앞쪽에 큰 값이 있으면 바로 인접한 값과 자리 교체
            while(j >= 0  && arr[j] > data) {
                arr[j+1] = arr[j];
                j--;
            }

            // 자리교체가 모두 끝났으면 마지막으로 arr[i]값이 들어갈 위치와 자리 교체
            arr[j+1] = data;
        }
    }
}