삽입정렬

1. 분석

• 이전값과 비교하여 작은 수를 앞으로 보내는 방식
• 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘

2. 기능

• 배열 1번째 자리부터 이전 값과 비교한다.

• n번 원소가 n-1번 원소보다 작으면 원소를 교환한다.

• 다음 원소로 이동하여 해당 원소와 그 이전 모든 원소를 비교한다.

3. 구현

public class InsertSort {

    static int[] sort(int[] arr){

        for(int i=1; i<arr.length; i++) {       // arr[1] ~ arr[4] 까지 반복
            for (int j = i-1; j >= 0; j--) {    // 이전 값 모두 비교(이전값 개수만큼 반복)
                if (arr[j+1] < arr[j]) {
                    int tmp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = tmp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
        return arr;
    }


    public static void main(String[] args) {
        int[] arr = {8,5,6,2,4};

        System.out.println(Arrays.toString(sort(arr)));
    }
} 
--- 결과 ---
[5, 8, 6, 2, 4]		배열 1번째 기준 : 8 > 5
[5, 6, 8, 2, 4]		배열 2번째 기준 : 6 < 8 (교환)
[5, 6, 8, 2, 4]		배열 2번째 기준 : 6 > 5
[5, 6, 2, 8, 4]		배열 3번째 기준 : 2 < 8 (교환)
[5, 2, 6, 8, 4]		배열 3번째 기준 : 2 < 6 (교환)
[2, 5, 6, 8, 4]		배열 3번째 기준 : 2 < 5 (교환)
[2, 5, 6, 4, 8]		배열 4번째 기준 : 4 < 8 (교환)
[2, 5, 4, 6, 8]		배열 4번째 기준 : 4 < 6 (교환)
[2, 4, 5, 6, 8]		배열 4번째 기준 : 4 < 5 (교환)

※ 참고자료 : https://en.wikipedia.org/wiki/Insertion_sort