[JAVA] 삽입 정렬(Insertion Sort)

[JAVA] 삽입 정렬(Insertion Sort)

삽입 정렬은 배열을 정렬된 부분과 정렬이 안 된 부분으로 나눈다.

i 번째를 정렬하기 전에 A[0 .. i - 1] 이 정렬되어 있다는 사실을 이용한다.

i 번째 반복에서 정렬이 안 된 부분의 첫 번째 요소 A[i]를 정렬된 부분 A[0 .. i - 1]에 삽입할 위치를 찾은 후 A[i]를 그 위치에 삽입시켜 A[0 .. i]를 정렬시킨다.

시간복잡도 O(N^2)

알고리즘

InsertionSort(A[0 .. n-1]) for (i = 1; i < n; i++) { insertElement = A[i] j = i - 1 while (j >= 0 and A[j] > insertElement) { A[j+1] = A[j] j = j - 1 } A[j+1] = insertElement }

JAVA

public class InsertionSort { public static void main(String[] args) { int[] intArray = {45, 89, 67, 92, 53, 74, 26, 80}; int i; System.out.print("정렬 전 배열: "); for (i = 0; i < intArray.length; i++) { System.out.print(intArray[i] + " "); } insertionSort(intArray); System.out.print("

정렬 후 배열: "); for (i = 0; i < intArray.length; i++) { System.out.print(intArray[i] + " "); } } public static void insertionSort(int[] A) { int i, j, insertElement; int n = A.length; for (i = 0; i < n; i++) { // 배열 A[0 .. i]를 재배열하여 정렬한다 insertElement = A[i]; j = i - 1; // A[i]를 A[0 .. i-1]에 삽입할 지수를 찾는다 while (j >= 0 && A[j] > insertElement) { A[j + 1] = A[j]; // A[j]를 오른쪽으로 한 자리 이동시킨다 j = j - 1; // A[i]를 찾은 위치에 삽입한다. A[j + 1] = insertElement; } } } }

from http://pekahblog.tistory.com/181 by ccl(S) rewrite - 2021-12-07 04:28:07