삽입정렬

삽입 정렬 (Insertion Sort)

이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘입니다. 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입합니다.

네이버 블로그 | ALOHA정보처리기사 실기 for 직장인 - 순서도_삽입정렬

정보처리기사 실기 for 직장인 - 순서도_삽입정렬

1. 순서도 - 삽입정렬 [문제] 아래의 <순서도> 는 10개의 자연수가 배열 A(6)에 정렬되지 않은 상태...

https://blog.naver.com/h850415/221492097636?trackingCode=blog_bloghome_searchlist

핵심 요소

•

정렬된 부분과 정렬되지 않은 부분으로 나누어 진행

•

각 원소를 적절한 위치에 삽입

•

in-place 알고리즘으로 추가 메모리가 거의 필요하지 않음

시간 복잡도

최선의 경우	O(n)
평균의 경우	O(n²)
최악의 경우	O(n²)

주요 특징

•

안정 정렬(Stable Sort)

•

작은 데이터셋에서 효율적

•

이미 정렬된 데이터에 대해 매우 효율적

•

적은 메모리 사용

예시 코드

직접 구현

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--;
            }
            arr[j + 1] = key; // 적절한 위치에 key 삽입
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 2, 9, 1, 5, 6 };
        insertionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
Java
복사