03. 삽입 정렬 (Insertion Sort)

정의

- 삽입 정렬은 두 번째 인덱스 부터 시작한다

- 해당 인덱스 (key 값) 앞에 있는 데이터 (B) 부터 비교해서 key 값이 더 작으면 B 값을 뒤 인덱스로 복사한다

- 이를 key 값이 더 큰 데이터를 만날 때 까지 반복하고, 큰 데이터를 만난 위치 바로 뒤에 Key 값을 이동

https://coding-factory.tistory.com/615

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해서 고안된 방법이 삽입정렬입니다. 삽입 정렬은 
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방법입니다. 
버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 기본적으로 버블정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 루팅을 작성할 시 버블정렬보다 탁월한 성능 효율을 보여줍니다. 
정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어납니다.

분석

삽입 정렬 (Insertion Sort)

public class InsertionSort {

    public static void main(String[] args) {

        int[] arr = {5, 2, 9, 7, 14, 3, 1};
        int count = 0;

        for (int i = 1; i < arr.length; i++) {
            int maxIdx = i;

            for (int j = i - 1; j >= 0; j--) {
                count++;

                if (arr[maxIdx] < arr[j]) {
                    int tmp = arr[maxIdx];
                    arr[maxIdx] = arr[j];
                    arr[j] = tmp;
                    maxIdx = j;
                } else {
                    break;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
        System.out.println("count = " + count);
    }
}

[1, 2, 3, 5, 7, 9, 14]
count = 16

• i = 1 (5)
  • j = 0 (2)
  • max < j
  • [2, 5, 9, 7, 14, 3, 1]
• i = 2 (9)
  • j = 1 (5)
    • max > j
    • break
• i = 3 (7)
  • j = 2 (9)
    • max < j 
    • [2, 5, 7, 9, 14, 3, 1]
  • j = 1 (5), max = 2 (7)
    • max > j
    • break

 

패캠 강의 코드

public class InsertionSort2 {
    public static void main(String[] args) {

        int[] arr = {5, 2, 9, 7, 14, 3, 1};
        int count = 0;


        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j > 0; j--) {
                count++;
                if (arr[j] < arr[j - 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                } else {
                    break;
                }
            }
        }

        System.out.println(Arrays.toString(arr));
        System.out.println("count = " + count);
    }
}

[1, 2, 3, 5, 7, 9, 14]
count = 16

max 위치를 알아내기 위해 max index 변수를 만들 필요가 없음