삽입 정렬 알고리즘 이해(Java 예제 포함)

삽입 정렬은 반복 정렬 알고리즘입니다. 정렬되지 않은 각 요소를 정렬된 하위 배열 내의 올바른 위치에 삽입하여 한 번에 한 요소씩 정렬된 하위 배열을 만듭니다. 카드 패를 정렬하는 것을 생각해 보세요. 정렬된 카드 하나로 시작한 다음 각 후속 카드를 이미 정렬된 카드 중 적절한 위치에 삽입합니다.

삽입 정렬 작동 방식

오름차순으로 정렬하려는 배열의 예를 들어 설명하겠습니다.

첫 번째 반복:

이미 정렬된 첫 번째 요소를 고려합니다. 알고리즘은 두 번째 요소로 시작됩니다.

2 < 이후 2를 8과 비교합니다. 8, 8을 오른쪽으로 이동하고 왼쪽에 2를 삽입합니다.

두 번째 반복:

6을 정렬된 하위 배열(2, 8)과 비교합니다. 6 < 8이므로 오른쪽으로 8교대합니다. 그러면 6 > 2, 6은 2의 오른쪽에 배치됩니다.

이 프로세스는 전체 배열이 정렬될 때까지 계속됩니다.

Java로 구현

import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

코드는 각 요소를 key으로 사용하여 반복됩니다. 그런 다음 key를 정렬된 부분의 요소와 비교하여 key의 올바른 위치를 찾을 때까지 더 큰 요소를 오른쪽으로 이동합니다.

예를 들어 두 번째 반복(i=2)에서는 다음과 같습니다.

key은 6입니다. while 루프는 올바른 위치를 찾을 때까지 요소를 이동합니다.

마지막으로 6이 삽입됩니다.

출력:

정렬되지 않은 배열: [8, 2, 6, 4, 9, 1] 정렬된 배열: [1, 2, 4, 6, 8, 9]

복잡성 분석

• 시간 복잡도:
  • 최상의 경우(O(n)): 이미 정렬된 배열입니다.
  • 평균 사례(O(n²)): 무작위로 배열된 요소
  • 최악의 경우(O(n²)): 역정렬된 배열.
• 공간 복잡도: O(1)(내부 알고리즘)

결론

삽입 정렬은 2차 시간 복잡도로 인해 대규모 데이터세트에는 비효율적입니다. 그러나 이는 간단한 알고리즘이며 작은 데이터세트나 거의 정렬된 데이터에서 잘 작동합니다.

위 내용은 삽입 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!