삽입 정렬(Insertion Sort)

삽입 정렬 알고리즘 동작 원리

1. 첫 번째 요소로 시작: 삽입 정렬은 배열의 첫 번째 요소를 이미 정렬된 부분 배열로 간주합니다. 배열의 첫 번째 요소는 이미 정렬되어 있다고 가정합니다.
2. 정렬된 부분 배열 확장: 다음 요소를 선택하고, 이미 정렬된 부분 배열에서 적절한 위치를 찾아 해당 요소를 삽입합니다. 이로써 두 번째 요소까지 정렬이 완료됩니다.
3. 반복 과정: 위의 과정을 배열의 끝까지 반복합니다. 배열의 모든 요소가 정렬된 부분 배열에 삽입되면, 정렬이 완료됩니다.

자바로 삽입 정렬 구현하기

자바를 사용하여 삽입 정렬을 구현해보겠습니다. 아래는 삽입 정렬을 자바 코드로 구현한 예시입니다.

public class InsertionSort {

    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int currentElement = array[i]; // 현재 요소 선택
            int j = i - 1; // 현재 요소 이전의 인덱스

            // 정렬된 부분 배열을 거꾸로 탐색하여 삽입할 위치를 찾음
            while (j >= 0 && array[j] > currentElement) {
                array[j + 1] = array[j]; // 더 큰 값을 오른쪽으로 이동
                j--;
            }
            
            array[j + 1] = currentElement; // 현재 요소를 올바른 위치에 삽입
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

• insertionSort 메서드는 배열을 인자로 받아 삽입 정렬을 수행합니다.
• currentElement는 현재 선택된 요소를 나타내며, j는 현재 요소의 이전 인덱스를 나타냅니다.
• while 루프는 정렬된 부분 배열을 거꾸로 탐색하면서, 현재 요소를 올바른 위치에 삽입합니다.
• 정렬된 배열을 오른쪽으로 한 칸씩 이동시키면서, 현재 요소가 삽입될 위치를 찾습니다.

 

실행 결과

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

정렬된 배열:
5 6 11 12 13