삽입 정렬
선택 정렬이란, 선택되지 않은 값들 중 가장 작은 값을 선택해서 계속해서 선택해서 정렬하는 것이 선택 정렬 알고리즘입니다.
삽입 정렬 나무 위키
삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.
각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다.
배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.
삽입 정렬 장단점
장점
•
구현이 간단하고 이해하기 쉽습니다.
•
정렬 중인 부분 배열이 이미 정렬되어 있다면, 삽입 연산이 빠르게 이루어져 더욱 빠르게 정렬됩니다.
•
소규모 데이터를 처리할 때는 매우 효율적입니다.
단점
•
배열의 크기가 큰 경우, 다른 정렬 알고리즘보다 성능이 떨어집니다.
•
배열의 역순으로 정렬된 경우, 삽입 연산이 매우 느리기 때문에 성능이 급격히 저하됩니다.
•
삽입 정렬은 안정적인 정렬 방법입니다. 하지만 특정한 조건에서는 불안정적인 정렬 방법으로 동작할 수 있습니다.
삽입 정렬의 정확한 구현
아래는 삽입 정렬을 설명하기 위한, 그림입니다.
•
가장 처음은 두 번째, 인덱스부터 시작합니다.
1.
선택된 인덱스에서 선택된 인덱스 전까지 자신이 들어갈 자리를 검사합니다.
2.
만약 자신보다 작다면, 다음 인덱스를 검사합니다.
3.
만약 자신보다 크다면, 현재 자신을 해당 인덱스 전으로 삽입합니다.
4.
만약 마지막 인덱스까지 검사했다면, 자신을 마지막 인덱스의 다음으로 삽입합니다.
5.
위 과정을 마지막 인덱스까지 반복합니다.
삽입 정렬의 코드
for (int i = 1; i < n; ++i)
{
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
C#
복사
1.
두 번째 원소부터 시작하여, 이전의 원소들과 비교합니다.
2.
이전의 원소들 중 자신보다 큰 값을 가지는 원소를 만날 때까지 반복하여 비교합니다.
3.
자신보다 큰 값을 가지는 원소를 만나면, 그 원소 바로 뒤에 삽입합니다.
4.
2 ~ 4 과정을 배열의 마지막 원소까지 반복합니다.
