자료구조 & 알고리즘
[Algorithm/Java] 삽입 정렬 (insertion sort)
삽입 정렬 (insertion sort) 삽입정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 평균 시간복잡도는 O(n^2)으로 느리지만, 구현하기 쉽다. 핵심 이론 정렬 대상(선택 값)을 현재 정렬된 데이터 범위 내에서 삽입할 위치를 찾는 것이 삽입 정렬의 핵심이다. 예제 첫 번째 데이터는 이미 정렬된 데이터이므로 넘어가고 두 번째 데이터부터 시작한다. (사이클 1) 두 번째 데이터 32를 선택하고, 정렬된 데이터 범위(0-1번 인덱스) 내에서 삽입할 위치를 찾는다. (0번 인덱스) 정렬된 위치 중 삽입할 자리를 만들기 위해 정렬범위 중 삽입할 자리의 오른쪽 데이터들을 옆으로 한 칸씩 이동시킨다. 따로 저장해 둔 선택 데이터를 삽입위치에 삽입한다. (사..
