삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

  알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 세 번째로 정리할 정렬 알고리즘은 삽입 정렬입니다.

 

삽입 정렬이란?

삽입 정렬은 배열을 순차적으로 탐색하면서 각 원소를 그 이전의 부분 배열에 적절한 위치에 삽입하여 정렬하는 알고리즘입니다.

 

동작 원리

1. 배열의 두 번째 원소부터 시작해서 첫 번째 원소와 비교한 후 적절한 위치에 삽입합니다.
2. 그 다음 원소를 비교하여 이미 정렬된 부분 배열의 적절한 위치에 삽입합니다.
3. 이 과정을 배열의 끝까지 반복합니다.

예시

[31, 25, 12, 22, 11] 이 처음 상태인 배열입니다.

 

[31, 25, 12, 22, 11] 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다.

 

[<25>, 31, 12, 22, 11] 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다.

 

[<12>, 25, 31, 22, 11] 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다.

 

[12, <22>, 25, 31, 11] 마지막 원소를 부분 리스트에서 적절한 위치에 섭입합니다.

 

[11, 12, 22, 25, 31] 정렬이 종료됩니다.

 

삽입 정렬 구현

public class InsertionSort{
    public static void main(String[] args) {
        int[] arr = new int[] {31, 25, 12, 22, 11};
        
        System.out.println("정렬 전 배열");
       	for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        
        // 두 번째 원소부터 시작하여 삽입 정렬 수행
        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;
        }
        
        System.out.println("정렬 후 배열");
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }
}

 

결과 화면