삽입 정렬(insertion sort) - goorm-6th-Als/for_study_Algorithm GitHub Wiki

알고리즘 개념 요약

손안의 카드를 정렬하는 방법과 유사하다

새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

알고리즘의 구체적인 개념

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
처음 Key 값은 두 번째 자료부터 시작한다.

알고리즘 예제

배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
1회전: 두 번째 자료인 5를 Key로 해서 그 이전의 자료들과 비교한다.

Key 값 5와 첫 번째 자료인 8을 비교한다. 8이 5보다 크므로 8을 5자리에 넣고 Key 값 5를 8의 자리인 첫 번째에 기억시킨다.

2회전: 세 번째 자료인 6을 Key 값으로 해서 그 이전의 자료들과 비교한다.

Key 값 6과 두 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 6이 있던 세 번째 자리에 기억시킨다.
Key 값 6과 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 작으므로 Key 값 6을 두 번째 자리에 기억시킨다.

3회전: 네 번째 자료인 2를 Key 값으로 해서 그 이전의 자료들과 비교한다.

Key 값 2와 세 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 2가 있던 네 번째 자리에 기억시킨다.
Key 값 2와 두 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 세 번째 자리에 기억시킨다.
Key 값 2와 첫 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 두 번째 자리에 넣고 그 자리에 Key 값 2를 기억시킨다.

4회전: 다섯 번째 자료인 4를 Key 값으로 해서 그 이전의 자료들과 비교한다.

Key 값 4와 네 번째 자료인 8을 비교한다. 8이 Key 값보다 크므로 8을 다섯 번째 자리에 기억시킨다.
Key 값 4와 세 번째 자료인 6을 비교한다. 6이 Key 값보다 크므로 6을 네 번째 자리에 기억시킨다.
Key 값 4와 두 번째 자료인 5를 비교한다. 5가 Key 값보다 크므로 5를 세 번째 자리에 기억시킨다.
Key 값 4와 첫 번째 자료인 2를 비교한다. 2가 Key 값보다 작으므로 4를 두 번째 자리에 기억시킨다.

알고리즘의 특징

장점 1.안정한 정렬 방법

레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점

비교적 많은 레코드들의 이동을 포함한다.
레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

시간잡

최선의 경우

비교 횟수

이동 없이 1번의 비교만 이루어진다.

외부 루프: (n-1)번

Best T(n) = O(n)

최악의 경우(입력 자료가 역순일 경우)

비교 횟수

외부 루프 안의 각 반복마다 i번의 비교 수행

외부 루프: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

교환 횟수

외부 루프의 각 단계마다 (i+2)번의 이동 발생

n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)

Worst T(n) = O(n^2) 출처