삽입 정렬

• 새로운 카드를 정렬되어 있는 카드 사이에 넣는 것과 비슷한 개념
• 두번째부터 시작해서 그 앞쪽 자료와 비교 했을때, 비교하려는 값이 더 작으면 그 자리에 넣고 원래 자리의 값은 뒤로 미는 것

예시

5 2 1 3 4 가 주어졌을때,
처음 비교할 값은 2

5 > 2이므로
2 5 1 3 4

그 다음 비교할 값은 1
5 > 1이므로
2 1 5 3 4
2 > 1 이므로
1 2 5 3 4

그 다음 비교할 값은 5
5 > 2 이므로 넘어감

그 다음은 3
5 > 3
1 2 3 5 4

그 다음은 4
5 > 4
1 2 3 4 5

구현

import java.util.*;

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

        int n = sc.nextInt();
        int[] lst = new int[n];

        for (int i = 0; i < n; i++)
            lst[i] = sc.nextInt();

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

        for (int i = 0; i < n; i++)
            System.out.print(lst[i] + " ");
    }
}

while문 속 내용이 조금 이해하기 어려웠는데
key값과 비교했을 때, key 값이 더 작으면 현재 비교 할 값을 뒤로 미뤄줘야 하니까 계속 뒤로 미뤄주는 거라고 생각,,
어차피 맨 처음의 lst[j + 1]는 key값으로 저장되어 있기 때문에
key값의 적절한 위치를 찾기 위해 key보다 작거나 같은 값이 나올때 까지 계속 그 큰 값들을 뒤로 미뤄주고
적절한 위치를 찾아 그 위치에 저장한다고 이해할 수 있다.