[JAVA] 알고리즘 : 정렬- 삽입정렬

 

삽입정렬

 

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 

원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬한다.

 

 

import java.util.*;

public class Main {
    public int[] solution(int n, int[] arr){
        for(int i=1; i<n; i++){ // 1.
            int tmp=arr[i], j;
            for(j=i-1; j>=0; j--){ // 2.
                if(arr[j]>tmp) arr[j+1]=arr[j];
                else break;
            }
            arr[j+1] =tmp; // 3.
        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr =new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();
        for(int x : T.solution(n,arr)) System.out.print(x+" ");
    }
}

 

 

 

1. 첫번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두번째 위치부터 탐색을 시작한다.

tmp에 임시로 해당 위치 값을 저장한다.

 

2. 이전 위치를 가리키는 j가 음수가 되지 않고, 이전 위치의 값이 1번에서 선택한 값보다 크다면, 서로 값을 교환한다.

그리고 j는 더 이전 위치를 가리키게된다.

 

3. 2번에서 반복문이 끝나고 난 뒤, j에는 현재 tmp값보다 작은 값들 중 제일 큰 값의 위치를 가리키게 된다.

따라서 j+1의 tmp값을 삽입해준다.