Gaon12: 시작

2023-04-05T01:24:15Z

시작

새 문서

== 개요 ==
삽입 정렬이란, 새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 알고리즘이다. 새로운 원소를 올바른 위치에 삽입 시켜나가는 과정을 모든 원소에 대해 수행하면 정렬이 완성된다.

== 예시 ==
<math>N = 8</math>인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때,
{| class="wikitable" style="text-align: center;"
|-
! rowspan="2" rawspan="2" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''3'''
|'''7'''
|'''2'''
|'''1'''
|'''6'''
|'''5'''
|'''4'''
|'''0'''
|}

0번째 인덱스에 있는 수는 그 자체로 정렬이 되어있으므로 그 다음 인덱스인 1번 인덱스부터 올바른 위치에 삽입을 시작한다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="2" rawspan="2" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''3'''
| style="background: #fff2cc; color: black;" |'''7'''
|'''2'''
|'''1'''
|'''6'''
|'''5'''
|'''4'''
|'''0'''
|}

인덱스 1번 이전에 있는 수와 1번을 비교했을 때, 인덱스 0번에 있는 수 3은 인덱스 1번에 있는 수 7보다 작으므로 자리 교환없이 삽입을 끝낸다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="4" rawspan="4" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''3'''
| style="background: #fff2cc; color: black;" |'''7'''
|'''2'''
|'''1'''
|'''6'''
|'''5'''
|'''4'''
|'''0'''
|-
|'''↘'''
|'''↘'''
|
|
|
|
|
|
|-
| style="background: #fff2cc; color: black;" |'''2'''
|'''3'''
|'''7'''
|
|
|
|
|
|}

이후, 인덱스 2번에 있는 수를 이전까지 정렬된 수열 [3, 7] 에 삽입한다. 인덱스 2번 이전에 있는 수들과 2번을 비교했을 때, 인덱스 1번에 있는 수 7은 인덱스 2번에 있는 수 2보다 크므로 한자리 뒤로 이동시킨다. 인덱스 0번에 있는 수 3도 인덱스 2번에 있던 수 2보다 크므로 한자리 뒤로 이동시킨다. 이후, 인덱스 2번에 있던 수 2를 제일 앞에 삽입한다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="4" rawspan="4" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''2'''
|'''3'''
|'''7'''
| style="background: #fff2cc; color: black;" |'''1'''
|'''6'''
|'''5'''
|'''4'''
|'''0'''
|-
|'''↘'''
|'''↘'''
|'''↘'''
|
|
|
|
|
|-
| style="background: #fff2cc; color: black;" |'''1'''
|'''2'''
|'''3'''
|'''7'''
|
|
|
|
|}

새로운 원소인 인덱스 3번에 있는 수를 이전까지 정렬된 배열 <math>[2, 3, 7]</math>에 삽입한다. 인덱스 2번에 있는 수 7은 인덱스 3번에 있는 수 1보다 크므로 7을 한자리 뒤로 이동시킨다. 인덱스 1번에 있는 수 3도 인덱스 1번에 있던 수 1보다 크므로 한자리 뒤로 이동시킨다. 인덱스 0번에 있는 수 2도 1보다 크므로 한자리 뒤로 이동시킨다. 마지막으로, 1을 올바른 위치 인덱스 0번에 삽입한다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="4" rawspan="4" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''1'''
|'''2'''
|'''3'''
|'''7'''
| style="background: #fff2cc; color: black;" |'''6'''
|'''5'''
|'''4'''
|'''0'''
|-
|
|
|
|'''↘'''
|
|
|
|
|-
|
|
|
| style="background: #fff2cc; color: black;" |'''6'''
|'''7'''
|
|
|
|}

새로운 원소인 인덱스 4번에 있는 수를 이전까지 정렬된 배열 <math>[1, 2, 3, 7]</math>에 삽입한다. 인덱스 3번에 있는 수 7은 인덱스 4번에 있는 수 6보다 크므로 한자리 뒤로 이동시킨다. 인덱스 3번에 있는 수 3은 인덱스 4번에 있던 수 6보다 작거나 같으므로 비교를 멈추고 6을 3 뒤에 위치시킨다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="4" rawspan="4" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''1'''
|'''2'''
|'''3'''
|'''6'''
|'''7'''
| style="background: #fff2cc; color: black;" |'''5'''
|'''4'''
|'''0'''
|-
|
|
|
|'''↘'''
|'''↘'''
|
|
|
|-
|
|
|
| style="background: #fff2cc; color: black;" |'''5'''
|'''6'''
|'''7'''
|
|
|}

새로운 원소인 인덱스 5번에 있는 수 5를 이전까지 정렬된 배열 <math>[1, 2, 3, 6, 7]</math>에 삽입한다. 인덱스 4번에 있는 수 7은 인덱스 5번에 있는 수 5보다 크므로 한자리 뒤로 이동시킨다. 인덱스 3번에 있는 수 6도 인덱스 5번에 있던 수 5보다 크므로 한자리 뒤로 이동시킨다. 인덱스 2번에 있는 수 3은 5보다 작거나 같으므로 비교를 멈추고 5를 3 뒤에 삽입한다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="4" rawspan="4" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''1'''
|'''2'''
|'''3'''
|'''5'''
|'''6'''
|'''7'''
| style="background: #fff2cc; color: black;" |'''4'''
|'''0'''
|-
|
|
|
|'''↘'''
|'''↘'''
|'''↘'''
|
|
|-
|
|
|
| style="background: #fff2cc; color: black;" |'''4'''
|'''5'''
|'''6'''
|'''7'''
|
|}

새로운 원소인 인덱스 6번에 있는 수 4를 이전까지 정렬된 배열 <math>[1, 2, 3, 5, 6, 7]</math>에 삽입한다. 인덱스 5번에 있는 수 7, 인덱스 4번에 있는 수 6, 인덱스 3번에 있는 수 5는 모두 4보다 크므로 한자리 씩 뒤로 이동한다. 인덱스 2번에 있는 수 3은 인덱스 6번에 있던 수 4보다 작거나 같으므로 비교를 멈추고 인덱스 2번의 뒤에 4를 삽입한다.

{| class="wikitable" style="text-align: center;"
|-
! rowspan="4" rawspan="4" |arr[idx]
| style="border-top:none; border-left:none; border-right:none;" |'''0'''
| style="border-top:none; border-left:none; border-right:none;" |'''1'''
| style="border-top:none; border-left:none; border-right:none;" |'''2'''
| style="border-top:none; border-left:none; border-right:none;" |'''3'''
| style="border-top:none; border-left:none; border-right:none;" |'''4'''
| style="border-top:none; border-left:none; border-right:none;" |'''5'''
| style="border-top:none; border-left:none; border-right:none;" |'''6'''
| style="border-top:none; border-left:none; border-right:none;" |'''7'''
|-
|'''1'''
|'''2'''
|'''3'''
|'''4'''
|'''5'''
|'''6'''
|'''7'''
| style="background: #fff2cc; color: black;" |'''0'''
|-
|'''↘'''
|'''↘'''
|'''↘'''
|'''↘'''
|'''↘'''
|'''↘'''
|'''↘'''
|
|-
| style="background: #fff2cc; color: black;" |'''0'''
|'''1'''
|'''2'''
|'''3'''
|'''4'''
|'''5'''
|'''6'''
|'''7'''
|}

=== 코드 ===
<syntaxhighlight lang='c++'>
#include <iostream>
using namespace std;

int N = 8;
int arr[8] = {1, 2, 3, 6, 7, 5, 4, 0};

void insertionSort() {

for (int i=1; i<N; i++) {
int key = arr[i];
int j;
for (j=i-1; j>=0 && arr[j] > key; j--)
arr[j+1] = arr[j];
arr[j+1] = key;
}
}

void printarr() {

for (int i=0; i<N; i++)
cout<<arr[i]<<" ";
cout<<endl;
}

int main() {

insertionSort();
printarr();
return 0;
}

/*output: 0 1 2 3 4 5 6 7*/
</syntaxhighlight>

== 시간 복잡도 ==
=== 최선의 경우 ===
모든 원소가 이미 정렬이 되어있는 경우, 외부 루프를 <math>N-1</math>번 도는 동안 비교 연산은 1번씩 수행된다.

따라서 최선의 경우, <math>T(n) = (N-1)*1</math>, <math>O(n) = n</math>이 된다.

=== 최악의 경우 ===
모든 원소가 역순으로 정렬되어 있는 경우, 외부 루프를 <math>N-1</math>번 도는 동안 비교연산은 <math>1, 2, ... , (N-1)</math>번 수행된다.

따라서 최악의 경우, <math>T(n) = 1+2+...+(N-1) = (N-1)*N/2</math>, <math>O(n) = n^2</math>이 된다.

== 안정성과 제자리성 ==
삽입정렬을 구현할 시, 비교대상의 원소가 새로운 원소보다 클 때만 한자리 뒤로 이동시키므로 동일한 원소의 우선순위는 처음 정렬과 동일하게 유지된다. 따라서 삽입정렬은 안정정렬(Stable sort)이다. 또한, 삽입정렬은 정렬해야 하는 배열 외 추가 메모리를 거의 사용하지 않으므로 제자리 정렬(In-place sort)이다.

[https://maramarathon.tistory.com/52 CC BY로 가져옴]


[[분류:알고리즘]] [[분류:정렬]]

삽입 정렬 - 편집 역사

Gaon12: 시작