삽입정렬

 

 

1. 배열의 두 번째 요소부터 시작한다.

2. 현재 요소를 정렬된 부분과 비교하며 올바른 위치를 찾아 삽입한다.

3. 위 과정을 배열의 끝까지 반복한다.

 

특징

• 시간 복잡도
  • 최악
    • O(n²) (역순 정렬일 경우)
  • 평균
    • O(n²)
  • 최선
    • O(n) (이미 정렬된 경우)
    • 모두 정렬이 되어있는 경우(Optimal)한 경우 한번씩만 비교
• 공간 복잡도
  • O(1) (추가 메모리가 필요하지 않음)
  • 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행

 

장점

• 알고리즘이 단순
• 이미 정렬된 데이터에는 O(n)의 시간 복잡도
• 안정 정렬
  • 동일한 값의 순서가 유지
• 작은 데이터셋에서는 효율적

 

단점

• 최악과 평균 시간 복잡도가 O(n²)
• 큰 데이터셋에는 비효율적
• 데이터가 많을수록 실행 시간이 급격히 증가

 

JAVA

import java.util.Arrays;

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 현재 요소 저장
            int key = arr[i];
            int j = i - 1;
            // 정렬된 부분에서 key보다 큰 값들을 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 올바른 위치에 key 삽입
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 6, 2};
        System.out.println("정렬 전: " + Arrays.toString(array));
        insertionSort(array);
        System.out.println("정렬 후: " + Arrays.toString(array));
    }
}

 

 

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        # 현재 요소 저장
        key = arr[i]
        j = i - 1
        # 정렬된 부분에서 key보다 큰 값들을 오른쪽으로 이동
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        # 올바른 위치에 key 삽입
        arr[j + 1] = key
    return arr


array = [5, 3, 8, 6, 2]
print("정렬 전:", array)
sorted_array = insertion_sort(array)
print("정렬 후:", sorted_array)