자바 삽입 정렬 알고리즘: 명확한 예제와 단계별 가이드

삽입 정렬 알고리즘이란?

삽입 정렬은 작거나 거의 정렬된 데이터셋에 적합한 직관적인 정렬 기법입니다. 각 반복에서 요소를 꺼내 앞의 요소들과 비교해 적절한 위치에 삽입합니다.

삽입 정렬은 최악/평균 경우 O(n²) 시간이지만, 이미 정렬된 배열에서는 선형 성능을 보입니다. 제자리 정렬이며 안정 정렬이고, 상수 추가 공간만 필요합니다.

삽입 정렬 알고리즘 과정

삽입 정렬 워크플로의 시각적 표현:

삽입 정렬 알고리즘 과정

자바 프로그램 예제: 삽입 정렬로 배열 정렬하기

package com.guru99;
public class InsertionSortExample {
    public static void main(String a[]) {
        int[] myArray = {860,8,200,9};
        System.out.println("삽입 정렬 전");
        printArray(myArray);
        insertionSort(myArray); // 삽입 정렬로 정렬
        System.out.println("삽입 정렬 후");
        printArray(myArray);
    }

    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("정렬 패스 번호 " + (i));
            int key = arr[i];
            int j = i-1;
            while ( (j > -1) && ( arr[j] > key ) ) {
                System.out.println("비교 " + key + " 와 " + arr[j]);
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
            System.out.println("요소 교환: 교환 후 새 배열");
            printArray(arr);
        }
    }

    static void printArray(int[] array){
        for(int i=0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

코드 출력:

삽입 정렬 전
860 8 200 9
정렬 패스 번호 1
비교 8 와 860
요소 교환: 교환 후 새 배열
8 860 200 9
정렬 패스 번호 2
비교 200 와 860
요소 교환: 교환 후 새 배열
8 200 860 9
정렬 패스 번호 3
비교 9 와 860
비교 9 와 200
요소 교환: 교환 후 새 배열
8 9 200 860
삽입 정렬 후
8 9 200 860