삽입 정렬 (Insertion Sort) - with Java

제목 : 삽입 정렬 (Insertion Sort) - with Java

---

기초적인 정렬 중, $ O(N^2) $ 를 가진 방법이다.

바로 직전에 선택 정렬 (Selection Sort) 에 대해서 주제를 다뤘는데,

선택 정렬과 삽입 정렬은,

현재 인덱스 이전이 완벽하게 정렬 되어 있는가? 로 나뉜다고 생각한다.

선택 정렬의 경우, 현재 인덱스 이전이 완벽하게 정렬되어 있다.

삽입 정렬의 경우, 현재 인덱스 이전 요소들에 한하여, 해당 영역은 정렬되어 있다.

하지만, 결과적으로 봤을 때 완벽하게 정렬되어 있지 않다.

또 다른 관점에서 둘을 비교해 보자.

Selection Sort 의 경우, i 번째 요소에 넣기 위한 "결과론적으로 완벽한" 요소를 찾는다.

Insertion Sort 의 경우, i 번째 요소는 1 번째 부터, i - 1 번째 까지의 영역 중 하나의 장소에 들어간다.

즉, 1 번째 부터, i - 1 번째까지의 요소는 "해당 영역에서만" 정렬되어 있다.

Insertion Sort 의 경우, 모든 루프가 끝날 때 까지, 어떠한 인덱스 범위도 완벽하게 정렬되어 있다 장담 할 수 없다.

삽입 정렬은 무엇이지?

기존의 포스팅들은 이미 삽입 정렬의 알고리즘과 구현에 대해서 다루고 있다.

하지만, 나는 관점 에 대해서 말해보고 싶다.

관점은 왜 다루나?

나는 이전에 알고리즘을 공부하는 도중, 모르는 것이 있으면 그냥 외워 버렸었다.

이러한 방식은 단기적으로 알고리즘 문제 자체를 푸는 데에는 효과적이었지만,

정렬의 본질적인 로직을 조금만 비틀어도 엄청나게 고민하고 있는 나 자신을 발견했다.

이후에 알고리즘을 이해하는 방식을 조금 바꾸었는데,

이 알고리즘은 어떤 관점에서 파생되었을까? 하는 것이다.

이 알고리즘이 있다. 라는 것을 배우는 것이 아니라, 이 알고리즘이 어떤 관점 or 상황에서 필요한가? 하는 것이다.

그래서 삽입 정렬에서 어떤 관점을 볼 수 있나?

나는 삽입 정렬(Insertion Sort) 이, 인간이 행하는 가장 흔한 정렬 중 하나라고 생각한다.

그래서, 우리는 특정 상황을 떠올려 볼 수 있다.

만약에 숫자 1 부터, 40 까지 적혀 있는 카드 혹은 종이를 손에 들고 있다고 가정한다.

이 숫자의 순서는 랜덤으로 배치되어 있으며, 오름차순으로 정리 할 것이다.

그렇다면, 우리는 어떤 관점으로 정렬 할 것인가?

• 정렬되지 않은 카드들을 전부 본 뒤, 가장 작은 수를 가진 카드를 따로 앞에 배치한다. - (선택 정렬 - Selection)
• 앞에서부터 카드를 하나씩 보며, 이미 정렬 해 놓은 카드들 사이에서 적절한 위치에 삽입한다. - (삽입 정렬 - Insertion)

내가 생각한 관점의 차이는 이러하다.

나라면, 선택 정렬보다는 삽입 정렬을 선택했을 것 같다.

삽입 정렬의 로직은?

이렇게 먼저 관점을 펼쳐놓고 로직을 생각 해 보니,

확실히 로직은 관점으로부터 파생되는 것 같다는 생각이 든다.

일단 생각은 제쳐두고, 어떠한 방식으로 정렬이 수행되는지 살펴보자.

index	0	1	2	3	4
value	5	2	3	4	1

이러한 배열이 존재하며, 우리는 이 값들을 정렬해야 한다고 가정 해 보자.

먼저, 삽입 정렬은 로직 수행을 위해 index 1 에서부터 시작한다.

예시로 든 상황을 보면 알 수 있듯이, "정렬 된 카드" 가 필요하기 때문이다.

어짜피 현재 정렬 된 카드가 5 하나뿐이라면, 이 또한 정렬되었다고 말할 수 있다!

index	0	1	2	3	4
value	5	2	3	4	1

숫자 2 와 5 를 비교해보자.

오름차순으로 정렬하므로, 2 가 당연히 5 앞에 와야 할 것이다.

그런데, 우리가 정해야 할 것이 있다.

컴퓨터는 사람과 달리, 숫자들을 펼쳐서 볼 수 없다.

즉, 컴퓨터는 숫자를 하나씩 뽑아서 보아야 한다는 사실을 알고, 다음 단계로 넘어가자.

index	0	1	2	3	4
value	2	5	3	4	1

정렬된 배열의 마지막 부분 5 와, 이제 정렬된 배열로 넣을 3 을 비교해보자.

당연히 현재 인덱스는 3 을 가르키므로, 정렬될 배열로 들어가야 한다.

이제 정해주어야 하는 것은, 어떻게 앞 부분이 정렬된 상태를 유지하나? 인 것이다.

만약에, 현재 인덱스가 가르키는 값이 3 이 아니라, 1 이라고 가정 해 보자.

그렇다면, 단순히 5 와 1 이 바뀐다고 해결되지 않는다. 2, 1, 5 는 정렬 된 상태가 아니다.

그렇다면, 앞 쪽의 배열은 어떻게 정렬된 상태를 유지하는가?

이는 조금 건너뛰어 실제 값 1 이 존재하는 인덱스 4 로 가보자.

index	0	1	2	3	4
value	2	3	4	5	1

자, 이제 선명하게 앞 쪽은 정렬된 배열이라는 것을 알 수 있고,

뒤 쪽은 아직 정렬되지 않은 부분이라는 것을 알 수 있다.

이제 다시 생각해보자. 어떻게 정렬해야 하는가?

당연히 1 은 배열의 가장 앞 부분에 와야 할 것이다.

1 을 맨 앞에 넣기 위해, IDX 0 과 IDX 4 를 그대로 바꿔버릴 순 없다. 정렬되지 않기 때문이다.

따라서, 현재 정렬된 배열에 넣을 숫자 1 에서부터 역 순으로 조회하며,

1 보다 큰 수라면, 해당 배열의 요소는 앞으로 Shift 한다.

하나의 루프 과정을 촘촘하게 파헤쳐 보자

이제, 1 을 넣기 위해, 숫자들을 Shift 하는 과정을 보자.

비교할 수는 따로 저장
1

5 는 1 보다 크다

index	0	1	2	3	4
value	2	3	4	5 ->	-> 5

4 는 1 보다 크다

index	0	1	2	3	4
value	2	3	4 ->	-> 4	5

3 은 1 보다 크다

index	0	1	2	3	4
value	2	3 ->	-> 3	4	5

2 는 1 보다 크다

index	0	1	2	3	4
value	2 ->	-> 2	3	4	5

결과

index	0	1	2	3	4
value	1	2	3	4	5

위의 과정을 통해 왼쪽의 배열이 어떻게 정렬된 상태를 유지하는 지 알 수 있었을 것이다.

만약에, 0 이 있었다면, 아마 1 은 0 을 발견하고, 1 은 0 보다 작다 조건이 발동되어 바로 뒤에 배치 될 것이다.

구현 - With Java

예제 입력, 예제 출력 은,

예제 입력	예제 출력
5 5 2 3 4 1	1 2 3 4 5

이라고 가정한다.

맨 위의 입력은 N 이고, 하나의 줄에 입력이 들어온다.

N 개의 줄에 걸쳐 입력이 들어오고, N 개의 줄로 결과를 출력해야 한다.

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

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

        // N 개의 요소를 정렬해야함.
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 삽입 정렬 - Insertion Sort 실행
        insertionSort(arr);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb.toString());
    }

    // 삽입 정렬 수행 함수 
    public static void insertionSort(int[] arr) {

        // 이미 정렬된 범위가 필요하므로, 처음이 아니라 그 다음부터 시작한다.
        for(int i = 1; i < arr.length; i++) {
            // 비교할 수를 선택하여 따로 저장 해 둔다.
            int currNum = arr[i];

            // j 를 for 문 안에서 소멸시키지 않고, 마지막에 재사용하기 위함.
            int j = i - 1;
            // j 는 0 이라는 끝 까지 가거나, 현재 지정 수가 arr[j] 보다 작을 때만 수행한다.
            for(; j >= 0 && arr[j] > currNum; j--) {
                // 비교할 정렬된 숫자를 추출한다.
                int diffNum = arr[j];

                // shift 수행 
                arr[j + 1] = arr[j];
            }
            // 지정된 위치로 숫자를 배치시킨다.
            arr[j + 1] = currNum;
        }
    }
}

---

참고 사이트

https://www.w3schools.com/dsa/dsa_algo_insertionsort.php