삽입 정렬(Insertion sort)

삽입 정렬(Insertion sort)

---

• 삽입 정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘
• 뒤섞여 있는 트럼프 카드를 순서대로 다시 정리하는 모습을 생각하면 이해하기 쉬움. 가장 왼쪽에서부터 한 장씩 카드를 꺼내서 이미 정렬된 카드들 중에 올바른 자리에 끼워넣는 것과 같음

 

동작 방식

1. 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눠줌
2. 정렬되지 않은 부분에서 원소를 선택하고, 그걸 정렬된 부분에 삽입함
3. 이걸 정렬되지 않은 부분이 없을 때까지 계속 반복함

 

동작 방식 예시

---

5 1 6 4 2 3

• 위의 숫자들을 트럼프 카드라고 생각

1. 앞의 카드 두 장을 선택하고, 오른쪽 카드가 왼쪽 카드보다 큰 지 비교해봄
2. 왼쪽이 5, 오른쪽이 1 이니까 오른쪽이 더 작음
3. 그러면 1을 뽑아서 5를 한 자리 옮긴 뒤에 5가 이동하면서 생긴 빈자리로 1을 삽입함

 

1 5 6 4 2 3

• 정렬 대상의 범위를 늘려서 크기가 3개가 됨 (1,5,6)

1. 3개 중 마지막 요소가 6인데 바로 앞의 5랑 비교하면 6이 크니까 제자리에 있음
2. 그 이전의 요소들(1,5) 는 이미 정렬된 상태니까 건들지 않음
3. 끝났으면 다시 반복 -> 정렬 대상 4개 (1,5,6,4)
4. 마지막 요소인 4가 앞의 6보다 작으니까 4를 뽑고, 4보다 큰 수는 한 칸씩 이동함
5. 정확한 위치에 4를 삽입함

 

1 4 5 6 2 3

• 이걸 계속 반복해서 1 2 3 4 5 6 이 되게 해줌

 

삽입정렬 예시

public class InsertionSort {

    public static void main(String[] args) {

    // 초기값 설정
    int[] array = {5, 1, 6, 4, 2, 3};

    // 삽입정렬 메서드 구현
        insertionSort(array);

        for (int num : array) {
            System.out.print(num + " "); //출력
        }
    }

    public static void insertionSort(int[] arr) {

    // 배열 길이를 저장
        int n = arr.length;

    // 반복문 이용해서 정렬하는데 1부터 시작해서 끝까지 반복해줌 (1,6,4,2,3 얘네는 정렬이 안 됐으니 커버들어감)
    // 0번째 인덱스인 5는 이미 정렬되어있다고 가정함 -> 왜냐면 2개를 비교해야하니까 !
        for (int i = 1; i < n; i++) {

    // 선택된 현재 원소 key
            int key = arr[i]; // 1
            int j = i - 1; // 정렬된 array 중 가장 큰 숫자를 j 로 지정 -> 0번째 인덱스만 있으니까 우선 5

            // 두 조건이 다 충족이 되어야만 루프 안으로 들어갈 수 있음

            while (j >= 0 && arr[j] > key) { // j 는 0번째 인덱스에 있으니까 조건 성립, j에 있는 값이 key 값보다 큼
        // 한칸 오른쪽으로 덮어씌움 (key를 다른 공간에 보관 안 하고 덮어 씌워도 되는가? yes 왜냐면 int key  안에 들어가있기 때문임
                arr[j + 1] = arr[j];

        // 그 후에 j 값을 모든 데이터와 비교하기 위해서 하나 줄어듦. 
                j--;
            }

    // 조건이 맞지않아 루프 안에 들어가지 못하면 임시 위치가 정해짐
    // 그리고 정렬된 array 의 크기가 하나 늘어나게 됨
            arr[j + 1] = key; 
        }
    }
}

시간 복잡도

---

삽입 정렬의 시간 복잡도는 비교 연산과 데이터의 이동에 의해 결정됨

• 최선의 경우 : 배열이 이미 정렬되어있을 때, 비교는 한 번씩만 이루어지니까 비교 횟수는 O(n)
• 최악의 경우 : 배열이 역순으로 정렬되어 있을 때 비교 횟수는 O(n^2)
• 평균적인 경우 : 평균적으로 적절한 위치로 이동시키기 위해서 비교 횟수는 O(n^2)

 

공간 복잡도

---

삽입 정렬의 공간 복잡도는 주로 배열 외에 추가적인 공간을 사용하는 경우 결정됨

• 주어진 배열 안에서 교환을 통해 정렬이 수행되니까 O(n)

 

장단점

---

장점

1. 작은 배열에서는 상대적으로 빠른 성능을 보임
2. 정렬된 배열에 대해서 효율적으로 처리 가능함
3. 정렬하고자 하는 배열 안에서 교환하는 방식이라 다른 메모리 공간을 필요로 하지 않는다 => 제자리 정렬
4. 안정 정렬(Stable Sort) 이다.

단점

1. 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적임
2. 배열의 크기가 커질 수록 다른 효율적인 정렬 알고리즘에 비해 느릴 수 있음