[do it 알고리즘] 삽입 정렬

원리

• 현재 비교하고자 하는 타깃과 그 이전에 정렬돼 있는 원소들과 비교하며 자리 교환하는 방법

과정

1. 현재 타깃과 타깃 앞에 위치한 원소들을 비교 (첫 번째 타깃은 두 번째 원소부터 시작)
2. 타깃이 되는 숫자가 앞에 위치한 원소들 중 정렬에 맞는 적절한 위치 찾기
3. 적절한 위치 뒤에 있는 원소들은 +1 하여 뒤로 밀어주기
4. 다음 타깃으로 이동하여 같은 방법 반복

코드

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {1,5,7,20,11,12,13,14,158,9,10};

        for(int i = 1; i < arr.length; i++) {
            int target = arr[i];
            int j = i - 1;
            while(j>=0 && arr[j] > target){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = target;
        }
        for(int i= 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

리뷰

적절한 위치 찾기와 뒤에 것을 밀어주는 것만 기억하자.