삽입 정렬

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 삽입정렬입니다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

 

출력

오름차순으로 정렬된 수열을 출력합니다.

 

예시 입력 1 

6
11 7 5 6 10 9

 

예시 출력 1

5 6 7 9 10 11

 

 

문제 해결

 

삽입 정렬이란?

이미 정렬된 배열과 비교해 현재 요소를 앞에서부터 비교해
자신의 위치를 찾아 삽입하는 알고리즘이라고 생각하면 됨

두 번째 자료부터 시작해 자신의 앞 자료들과 비교해 삽입할 위치를 찾아 넣고 자료를 뒤로 옮긴다.

- 2번째 자료는 => 1번째 자료 

- 3번째 자료는 => 2, 1번째 자료

- 4번째 자료는 3, 2, 1번째 자료와 비교한 후 자료가 삽입될 위치를 찾는 것이다.

 

자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
즉 key값은 2번째 인덱스부터 시작되며, key값이 자료의 길이만큼 이동되었을 때 정렬이 완성된다.

 

그럼 이를 코드로 구현해보자.

key 바로 앞 요소부터 시작하여 배열 시작 지점(인덱스0)까지 거슬러 올라가며 비교하는 방식으로 구현된다.

 

for(int i = 0; i < N-1; i++) {
    int keyIndex = i+1; //2번째 인덱스부터 key값 시작.
    int key = num[keyIndex];
    int j = i;

 

삽입 정렬은 key가 존재하므로 keyIndex라는 변수를 만들어주었다. 2번째 인덱스부터 시작한다고 했으니 이는 i+1로 초기화해주었다. (for문을 i로 돌 때) 그럼 key는 num[keyIndex]가 된다.

 key를 삽입할 위치를 찾기 위해 사용할 변수로 j를 만들어주었고, i를 넣어주었다.

 

while (j >= 0 && num[j] > key){ //'j >= 0' 조건 안 걸어주면 ArrayIndexOutOfBoundsException 발생. 주의
    num[j+1] = num[j]; // 오른쪽으로 한 칸 이동
    j--;
}

• while문은 정렬된 부분의 끝에서 시작한다. (초기에 j = i, 여기서 i는 정렬된 부분의 마지막 인덱스).
• j가 0 이상이고 num[j]가 key보다 클 때까지 루프를 반복한다. 두 조건이 모두 만족되면 key는 j의 왼쪽 어딘가에 삽입되어야 하므로 num[j]를 오른쪽으로 한 칸 이동시켜 공간을 만든다.
• 이를 정확한 삽입 위치를 찾을 때까지 반복한다 => 즉, j가 0 아래로 떨어지거나 key보다 작거나 같은 수가 나타날 때까지 (while문 빠져나갈 때까지)

 

num[j+1] = key; //while문 빠져나갔을 때의 key를 num[j+1]에 삽입

• 루프가 끝나면 j+1가 key의 정확한 위치이므로 여기에 key를 삽입한다.
• 이 위치는 더 작은 요소 바로 뒤거나 정렬된 부분의 모든 요소가 key보다 클 경우 시작 부분이 됩니다.

 

최종 코드

 

import java.util.Scanner;

public class P03_삽입정렬 {
    public static void main(String[] args) {

        /** key를 앞에서부터 비교하며 자신의 위치를 찾아 삽입
         *  key값은 2번째 인덱스부터 시작됨 **/

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] num = new int[N];

        for(int i = 0; i < N; i++){
            num[i] = in.nextInt();
        }

        for(int i = 0; i < N-1; i++) {
            int keyIndex = i+1; //2번째 인덱스부터 key값 시작.
            int key = num[keyIndex];
            int j = i;

            while (j >= 0 && num[j] > key){ //'j >= 0' 조건 안 걸어주면 ArrayIndexOutOfBoundsException 발생. 주의
                num[j+1] = num[j]; // 오른쪽으로 한 칸 이동
                j--;
            }
            num[j+1] = key; //while문 빠져나갔을 때의 key를 num[j+1]에 삽입
        }
        for (int i : num) {
            System.out.print(i + " ");
        }

    }
}