삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

삽입 정렬(Insertion Sort)

정렬되어 있지 않은 부분의 왼쪽 끝에서 삽입할 원소를 찾아서 정렬되어 있는 부분의 적절한 위치에 삽입

정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로써, 정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어든다.

이를 반복하면 결국 정렬 안 된 부분에는 아무 원소도 남지 않고 정렬된 부분에 모든 원소가 존재

정렬 방법 정렬되어 있지 않은 부분의 왼쪽에서 삽입할 원소 k 선택 빈자리 확보를 위해 k를 꺼내서 임시 장소에 보관 정렬되어 있는 부분에서 k보다 큰 원소들을 오른쪽으로 이동하여 k가 들어갈 빈자리 확보 확보된 빈자리에 k삽입 모든 원소들이 정렬될 때 까지 반복

안정된 정렬 방법

많은 이동 횟수(레코드가 클 경우 불리하다)

이미 정렬이 어느정도 되어 있으면 효율적

시간 복잡도 최상의 경우(이미 정렬되어 있는 경우) 비교 : n-1번 이동 : 2(n-1)번 최악의 경우(역순으로 정렬되어 있는 경우 모든 단계에서 앞에 놓은 자료 전부 이동) 비교 : n(n-1) / 2 이동 : n(n-1) / 2 + 2(n-1)

삽입 정렬 예제 코드

InsertionSort.java

public class InsertionSort { public static void main(String[] args) { int [] arr = {5,2,8,3,1}; insertSort(arr); System.out.println(Arrays.toString(arr)); } static void insertSort(int[] arr) { for(int i = 1; i= 0 && temp < arr[index]) { // 이전 원소를 한 칸씩 뒤로 이동 arr[index+1] = arr[index]; index--; } arr[index+1] = temp; } } }

from http://5bong2-develop.tistory.com/57 by ccl(A) rewrite - 2021-12-01 11:01:31