이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
삽입 정렬은 한 번에 하나씩 새 항목을 가져와 이미 정렬된 목록의 올바른 위치에 삽입하는 간단한 정렬 알고리즘입니다. 퀵 정렬, 힙 정렬 또는 병합 정렬과 같은 고급 알고리즘보다 큰 목록에서 훨씬 덜 효율적입니다. 그러나 작은 목록에는 매우 효율적이며 더 정교한 알고리즘의 일부로 자주 사용됩니다. 또한 동일한 키를 가진 항목의 순서를 유지하는 안정적인 정렬입니다.
다음은 삽입 정렬의 간단한 예입니다. 정렬되지 않은 숫자 목록으로 시작합니다.
5, 2, 4, 6, 1, 3
이 목록을 정렬하려면 먼저 두 번째 항목(2
)을 가져와 이미 정렬된 목록(5, 2, 4, 6, 1, 3
)의 올바른 위치에 삽입합니다. 그런 다음 세 번째 항목(4
)을 가져와 이미 정렬된 목록(2, 4, 5, 6, 1, 3
)의 올바른 위치에 삽입합니다. 전체 목록이 정렬될 때까지 이런 식으로 계속합니다.
1, 2, 3, 4, 5, 6
삽입 정렬 알고리즘은 몇 줄의 코드로 구현할 수 있습니다. 다음은 C로 간단하게 구현한 것입니다.
void insertion_sort(int array[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = array[i];
j = i-1;
while (j >= 0 && array[j] > temp) {
array[j+1] = array[j];
j--;
}
array[j+1] = temp;
}
}
이 구현은 배열을 제자리에서 정렬합니다. 즉, 새 배열을 만들지 않고 배열을 제자리에서 정렬합니다.
이 구현을 테스트하기 위해 난수 배열을 만들고 삽입 정렬 알고리즘을 사용하여 정렬할 수 있습니다. 그런 다음 정렬된 배열을 인쇄하여 실제로 정렬되었는지 확인할 수 있습니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void insertion_sort(int array[], int n);
int main(void)
{
int i, n = 10;
int array[n];
srand(time(NULL));
for (i = 0; i < n; i++) {
array[i] = rand() % 100;
}
insertion_sort(array, n);
for (i = 0; i < n; i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
이 코드를 실행하면 다음과 같은 결과가 나타납니다.
2 4 5 8 12 23 37 38 39 45
배열이 실제로 정렬된 것을 볼 수 있습니다.
삽입 정렬의 최악의 시간 복잡도는 'O(n^2)'입니다. 이것은 배열이 역순으로 정렬될 때 발생합니다. 최상의 경우 시간 복잡도는 'O(n)'이며 배열이 이미 정렬된 경우 발생합니다.
삽입 정렬은 키가 같은 항목의 순서를 유지하는 안정적인 정렬입니다. 또한 내부 정렬이므로 새 배열을 만들지 않고 배열을 제자리에서 정렬합니다.
선호하는 프로그래밍 언어로 삽입 정렬 알고리즘을 구현합니다.
삽입 정렬 알고리즘을 수정하여 단일 연결 목록을 정렬합니다.
삽입 정렬 알고리즘을 수정하여 문자열 배열을 정렬합니다.