Intro

---

오늘은 알고리즘 정렬 방식 중 하나인 Insertion Sort(삽입 정렬)에 대해서 정리를 해볼까 한다.

Body

---

Insertion Sort: 특정 Index 앞의 모든 요소가 올바르게 정렬되어 있다는 가정하에 올바른 위치를 찾아 삽입하는 정렬 방식

예를 들어, 4 9 10 15 18 20 13 1 5 4라는 숫자 배열을 정렬하고자 할 때 5번 index인 20까지는 올바르게 오름차순으로 정렬되어 있다.

이 때 6번 index의 값인 13을 올바른 자리에 삽입하는 정렬이 되겠다.

How?

먼저, 올바른 자리를 찾아야 하는 특정 index의 입장에서 생각을 해보면 앞부분(왼쪽)에 있는 숫자들을 순회하다가 자신보다 작은 숫자가 나타난다면 그 자리에서 삽입을 실행해주면 된다.

특정 index 값의 입장에서 순회하다가 Swap하는 Code

간단한 Pseudo Code를 짜보면 다음과 같다.

# k번 index의 입장에서 순회하다가 삽입하는 Pseudo Code
public static void process_with_positioin_of_some_index(A, k):
	# A : 배열
    # k : 특정 index
    key, j = A[k], k-1
    whlie j >= 0 and A[j] > key:
    	A[j+1] = A[j]
        j--
	A[j+1] = key

이제 이 코드를 배열을 순회하는 반복문에 적용시켜 주면 된다

Java 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] A = new int[n];
        // input
        for (int i = 0; i < n; i++){
            A[i] = sc.nextInt();
        }

        // function call
        int[] result = insertion_sort(A);

        // output
        for(int i = 0; i< n; i++){
            System.out.print(result[i] + " ");
        }
    }

    private static int[] insertion_sort(int[] A){
        int size = A.length;
        for (int i = 1; i < size; i++){
            int j = i-1, key = A[i];
            while(j >= 0 && A[j] > key){
                A[j+1] = A[j];
                j--;
            }
            A[j+1] = key;
        }
        return A;
    }
}