기본 정렬 알고리즘 구현: 삽입 정렬 (Java)

삽입 정렬

삽입 정렬

- 삽입정렬(insertion sort), 배열의 요소를 하나씩 제자리에 삽입하면서 정렬하는 알고리즘

 

시간 복잡도

최선: O(n)

최악: O(n^2) 

 

시간 복잡도

 

특징

코드 단순

 

기본 과정

1. 1부터 시작

• 첫 번째는 이미 정렬된 것으로 간주

2. key보다 큰 값들은 오른쪽으로 이동

3. key를 빈 자리에 삽입반복

 

코드(오름차순)

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        // 두 번째 요소부터 시작 (첫 번째는 이미 정렬된 것으로 간주)
        for(int i = 1; i < n; 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[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
    }

}