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

삽입 정렬(Insertion Sort)은 비교 기반의 정렬 알고리즘으로, 배열의 각 요소를 순차적으로 선택하여 적절한 위치에 삽입하면서 배열을 정렬하는 방식이다. 이 알고리즘은 현재 배열의 일부분을 이미 정렬된 상태로 유지하면서, 새로운 요소를 삽입하는 방식으로 작동한다. 거의 정렬된 데이터에서 매우 효율적으로 동작하며, 구현이 간단하고 직관적인 특징이 있다.

동작 방식

 

• 초기 상태: 첫 번째 요소는 이미 정렬된 것으로 가정한다.
• 두 번째 요소부터 시작: 배열의 두 번째 요소를 선택한다.
• 왼쪽에 있는 정렬된 부분과 비교: 선택한 요소를 왼쪽의 정렬된 부분에 삽입할 적절한 위치를 찾기 위해 비교한다.
• 삽입: 비교하여 자신보다 큰 값들은 한 칸씩 오른쪽으로 이동시키고, 자신의 자리를 찾으면 그 위치에 삽입한다.
• 반복: 이 과정을 배열의 끝까지 반복한다.

장점

 

• 간단하고 구현이 쉬움: 알고리즘 구조가 직관적이기 때문에 간단하게 구현할 수 있다.
• 거의 정렬된 데이터에 효율적: 데이터가 이미 정렬되어 있거나 거의 정렬된 경우 매우 빠르게 동작한다.
• 제자리 정렬(In-place sorting): 별도의 메모리를 거의 사용하지 않는다. 정렬을 위한 추가적인 메모리가 필요하지 않기 때문에 메모리 효율적이다.
• 안정성(Stable): 동일한 값들이 원래의 순서를 유지한다.

단점

 

• 비효율성: 요소를 삽입할 때 왼쪽 부분의 요소들을 모두 비교해야 하므로, 큰 배열이나 역순으로 정렬된 배열에서 성능이 좋지 않다.
• 시간 복잡도: 최악의 경우 시간 복잡도는 O(n²)로, 배열이 역순으로 정렬되어 있을 경우 많은 비교와 이동이 발생한다.

※ 시간 복잡도
최선의 경우 (O(n)): 배열이 이미 정렬되어 있을 경우, 삽입할 때 비교가 거의 발생하지 않으므로 선형 시간에 완료
평균 및 최악의 경우 (O(n²)): 일반적으로 요소를 삽입할 위치를 찾기 위해 많은 비교와 이동이 필요할 때는 이중 루프가 사용되므로, 시간 복잡도는 O(n²)가 된다.

 

코드

public class InsertionSort {

    // 삽입 정렬 알고리즘
    public static void insertionSort(int[] arr) {
        // 1. 배열의 두 번째 요소부터 끝까지 순차적으로 탐색
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];  // 현재 삽입할 값 (key)
            int j = i - 1;  // key 앞에 있는 요소들의 인덱스

            // 2. 현재 key 값보다 큰 값들을 오른쪽으로 한 칸씩 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];  // 요소를 한 칸씩 오른쪽으로 이동
                j--;  // 한 칸 왼쪽으로 이동하며 비교
            }
            
            // 3. key 값을 적절한 위치에 삽입
            arr[j + 1] = key;
        }
    }

    // 배열 출력 메서드
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 메인 메서드
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};

        System.out.println("정렬 전 배열:");
        printArray(arr);

        insertionSort(arr);  // 삽입 정렬 호출

        System.out.println("정렬 후 배열:");
        printArray(arr);
    }
}

반응형

코드 설명

1. insertionSort 메서드:
   • 이 메서드는 배열 arr의 두 번째 요소부터 시작해서 마지막 요소까지 탐색하며 정렬한다.
   • key: 현재 삽입하고자 하는 값
   • j: key의 앞에 있는 요소들을 비교하는 인덱스
2. 외부 for문:
   • 배열의 두 번째 요소부터 탐색을 시작하며, 현재 요소가 적절한 위치에 삽입될 때까지 앞의 요소들과 비교한다.
3. 내부 while문:
   • 현재 삽입하고자 하는 값 key와 그 이전의 값들을 차례로 비교한다.
   • arr [j] > key이면, arr [j]를 오른쪽으로 한 칸 옮기고, j를 하나씩 줄이면서 비교를 이어간다.
   • 이 과정을 반복하다가 key가 더 작은 값을 만나거나 배열의 시작에 도달하면, while문을 탈출한다.
4. key 삽입:
   • 더 이상 비교할 필요가 없을 때, key 값을 적절한 위치에 삽입한다. arr [j + 1] 자리가 key의 위치가 된다.

동작 과정 예시

배열 {12, 11, 13, 5, 6}을 정렬하는 과정

1. 첫 번째 단계 (i = 1):
   • key = 11, j = 0
   • arr [0] = 12는 key(11) 보다 크므로 오른쪽으로 이동
   • key(11)은 arr [0]에 삽입
   • 결과: {11, 12, 13, 5, 6}
2. 두 번째 단계 (i = 2):
   • key = 13, j = 1
   • arr [1] = 12는 key(13) 보다 작으므로 이동하지 않고 key는 제자리에 위치
   • 결과: {11, 12, 13, 5, 6}
3. 세 번째 단계 (i = 3):
   • key = 5, j = 2
   • arr [2] = 13은 key(5) 보다 크므로 오른쪽으로 이동
   • arr [1] = 12도 key(5) 보다 크므로 오른쪽으로 이동
   • arr [0] = 11도 key(5) 보다 크므로 오른쪽으로 이동
   • key(5)는 arr [0]에 삽입
   • 결과: {5, 11, 12, 13, 6}
4. 네 번째 단계 (i = 4):
   • key = 6, j = 3
   • arr [3] = 13은 key(6) 보다 크므로 오른쪽으로 이동
   • arr [2] = 12도 key(6) 보다 크므로 오른쪽으로 이동
   • arr [1] = 11은 key(6) 보다 작으므로 이동하지 않고 key는 arr [2]에 삽입
   • 결과: {5, 6, 11, 12, 13}

삽입 정렬은 작은 데이터셋이나 이미 어느 정도 정렬된 데이터를 처리할 때 유용하며, 큰 데이터셋에서는 효율적이지 않을 수 있다.