설명

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

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

코드

public class InsertSort {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }
        solution(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
    public static void solution(int[] arr){
        int length = arr.length;
        for(int i=1; i<length; i++){
            int temp = arr[i];
            int j=0;
            for(j=i-1; j>=0; j--){
                if(arr[j]>temp)
                    arr[j+1] = arr[j];
                else
                    break;
            }
            arr[j+1] = temp;
        }
    }
}

삽입 정렬은 정렬될 값이 자신의 자리를 찾아가는 정렬인데. 그렇기 때문에 다른 정렬과는 다르게 swap 대신 temp를 사용한다. 그리고 temp보다 arr[j]의 값이 더 클 경우 arr[j]를 arr[j+1]에 대입함으로써 배열을 한칸씩 뒤로 민다고 생각하면 좋을 것 같다. 그 후 j의 값에 temp에 담겨있는 arr[i]의 값을 다시 넣어주는 것으로 정렬이 종료되는 알고리즘이다. 이 부분은 실제로 실행하면서 디버깅을 해보는 것을 추천한다. 그래야 로직을 이해해 볼 수 있으니까!

삽입 정렬은 처음 이해하긴 어렵지만 실제로 돌아가는 구조를 봐보면 그냥 한칸씩 뒤로 밀고 밀다가 자기 위치를 찾았을 때 그 위치에 자신을 넣는 정렬이라고 생각하면 쉬울것 같다.

예시로

4
4 3 2 1

을 입력했을 때 실행을 함께 봐보자

i = 1
이므로 temp에는 arr[1]의 값인
temp = 3
이 들어간다. 그리고 j는 0부터 실행되어 비교하게 되고 arr[0] = 4이므로
if(arr[j]>temp) = true
가 된다. 그래서 arr[j+1] = arr[j]가 실행되므로
arr[1] = arr[0]
arr[1] = 4
를 모두 실행했고 이때 배열을 살펴보면
{4,4,2,1}
이 되었다. for문이 모두 종료된 이후 j는 j--로 인해 -1이 되었고 for문 이후의 arr[j+1] = temp 실행에 의해
arr[0] = temp(=3)
이 실행되고 이때 배열을 다시 한번 살펴보면
{3,4,2,1}
이 되었다 이렇게 계속해서 반복해 나가면
{1,2,3,4}
로 정렬할 수 있을 것이다.

나머지 동작도 궁금하다면 직접 디버깅을 찍어보고 확인해 보는 것을 추천한다!