삽입 정렬은 반복 정렬 알고리즘입니다. 정렬되지 않은 각 요소를 정렬된 하위 배열 내의 올바른 위치에 삽입하여 한 번에 한 요소씩 정렬된 하위 배열을 만듭니다. 카드 패를 정렬하는 것을 생각해 보세요. 정렬된 카드 하나로 시작한 다음 각 후속 카드를 이미 정렬된 카드 중 적절한 위치에 삽입합니다.
삽입 정렬 작동 방식
오름차순으로 정렬하려는 배열의 예를 들어 설명하겠습니다.
첫 번째 반복:
이미 정렬된 첫 번째 요소를 고려합니다. 알고리즘은 두 번째 요소로 시작됩니다.
2 < 이후 2를 8과 비교합니다. 8, 8을 오른쪽으로 이동하고 왼쪽에 2를 삽입합니다.
두 번째 반복:
6을 정렬된 하위 배열(2, 8)과 비교합니다. 6 < 8이므로 오른쪽으로 8교대합니다. 그러면 6 > 2, 6은 2의 오른쪽에 배치됩니다.
이 프로세스는 전체 배열이 정렬될 때까지 계속됩니다.
Java로 구현
<code class="language-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; } } }</code>
코드는 각 요소를 key
으로 사용하여 반복됩니다. 그런 다음 key
를 정렬된 부분의 요소와 비교하여 key
의 올바른 위치를 찾을 때까지 더 큰 요소를 오른쪽으로 이동합니다.
예를 들어 두 번째 반복(i=2)에서는 다음과 같습니다.
key
은 6입니다. while
루프는 올바른 위치를 찾을 때까지 요소를 이동합니다.
마지막으로 6이 삽입됩니다.
출력:
정렬되지 않은 배열: [8, 2, 6, 4, 9, 1] 정렬된 배열: [1, 2, 4, 6, 8, 9]
복잡성 분석
결론
삽입 정렬은 2차 시간 복잡도로 인해 대규모 데이터세트에는 비효율적입니다. 그러나 이는 간단한 알고리즘이며 작은 데이터세트나 거의 정렬된 데이터에서 잘 작동합니다.
위 내용은 삽입 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!