다음 숫자를 고려하십시오.
50 60 30 10 80 70 20 40
이 목록을 오름차순으로 정렬하면 다음과 같습니다.
10 20 30 40 50 60 70 80
내림차순으로 정렬하면 다음과 같습니다.
80 70 60 50 40 30 20 10
삽입 정렬은 목록을 오름차순 또는 내림차순으로 정렬하는 데 사용되는 정렬 알고리즘입니다. 이 문서에서는 오름차순 정렬만 다룹니다. 내림차순 정렬은 이 문서에 제공된 것과 동일한 논리를 따릅니다. 이 문서의 목적은 삽입 정렬을 설명하는 것입니다. 프로그래밍은 C의 다음 예제에서 수행됩니다. 여기서는 하나의 배열을 사용하여 삽입 정렬을 설명합니다.
삽입 정렬 알고리즘
정렬되지 않은 목록이 제공됩니다. 목표는 동일한 목록을 사용하여 목록을 오름차순으로 정렬하는 것입니다. 동일한 배열을 사용하여 정렬되지 않은 배열을 정렬하는 것을 제자리 정렬이라고 합니다. 0 기반 인덱싱이 여기에 사용됩니다. 단계는 다음과 같습니다.
-
- 목록은 처음부터 스캔됩니다.
- 스캔이 진행되는 동안 이전 번호보다 작은 숫자는 이전 번호와 교환됩니다.
- 이 교환은 더 이상 교환할 수 없을 때까지 목록을 따라 계속됩니다.
- 스캔이 끝에 도달하면 정렬이 완료됩니다.
삽입 정렬 그림
시간 복잡도를 다룰 때 일반적으로 고려되는 최악의 경우입니다. 이전 목록에 대한 최악의 배열은 다음과 같습니다.
80 70 60 50 40 30 20 10
0에서 7까지의 인덱스를 가진 8개의 요소가 있습니다.
인덱스 0에서 스캔은 80으로 이동합니다. 이것은 하나의 이동입니다. 이 하나의 움직임이 수술입니다. 지금까지 총 하나의 작업이 있습니다(하나의 이동, 비교 및 스왑 없음). 결과는 다음과 같습니다.
| 80 70 60 50 40 30 20 10
인덱스 1에서 70으로 이동합니다. 70은 80과 비교됩니다. 70과 80은 교환됩니다. 하나의 움직임은 하나의 작업입니다. 하나의 비교도 하나의 작업입니다. 하나의 스왑도 하나의 작업입니다. 이 섹션에서는 세 가지 작업을 제공합니다. 지금까지 총 4개의 작업이 있습니다(1 + 3 = 4). 결과는 다음과 같습니다.
70 | 80 60 50 40 30 20 10
인덱스 2에서 60으로 이동합니다. 60은 80과 비교되고 60과 80은 교환됩니다. 60을 70과 비교한 다음 60과 70을 바꿉니다. 하나의 움직임은 하나의 작업입니다. 두 개의 비교는 두 개의 연산입니다. 두 개의 스왑은 두 개의 작업입니다. 이 섹션에서는 5가지 작업을 제공합니다. 지금까지 총 9개의 작업이 있습니다(4 + 5 = 9). 결과는 다음과 같습니다.
60 70 | 80 50 40 30 20 10
인덱스 3에서 50으로 이동합니다. 50은 80과 비교되고 50과 80은 교환됩니다. 50을 70과 비교한 다음 50과 70을 바꿉니다. 50을 60과 비교한 다음 50과 60을 바꿉니다. 하나의 움직임은 하나의 작업입니다. 세 가지 비교는 세 가지 작업입니다. 3개의 스왑은 3개의 작업입니다. 이 섹션에서는 7가지 작업을 제공합니다. 지금까지 총 16개의 작업이 있습니다(9 + 7 = 16). 결과는 다음과 같습니다.
50 60 70 | 80 40 30 20 10
인덱스 4에서 40으로 이동합니다. 40은 80과 비교되고 40과 80은 교환됩니다. 40을 70과 비교한 다음 40과 70을 바꿉니다. 40을 60과 비교한 다음 40과 60을 바꿉니다. 40을 50과 비교한 다음 40과 50을 바꿉니다. 하나의 움직임은 하나의 작업입니다. 네 가지 비교는 네 가지 작업입니다. 4개의 스왑은 4개의 작업입니다. 이 섹션에서는 9가지 작업을 제공합니다. 지금까지 총 25개의 작업이 있습니다(16 + 9 = 25). 결과는 다음과 같습니다.
40 50 60 70 80 | 30 20 10
인덱스 5에서 30으로 이동합니다. 30은 80과 비교되고 30과 80은 교환됩니다. 30을 70과 비교한 다음 30과 70을 바꿉니다. 30을 60과 비교한 다음 30과 60을 바꿉니다. 30을 50과 비교한 다음 30과 50을 바꿉니다. 30을 40과 비교한 다음 30과 40을 바꿉니다. 하나의 움직임은 하나의 작업입니다. 5번의 비교는 5번의 연산입니다. 5개의 스왑은 5개의 작업입니다. 이 섹션에서는 11가지 작업을 제공합니다. 지금까지 총 36개의 작업이 있습니다(25 + 11 = 36). 결과는 다음과 같습니다.
30 40 50 60 70 80 | 20 10
인덱스 6에서 20으로 이동합니다. 20은 80과 비교되고 20과 80은 교환됩니다. 20을 70과 비교한 다음 20과 70을 바꿉니다. 20을 60과 비교한 다음 20과 60을 바꿉니다. 20을 50과 비교한 다음 20과 50을 바꿉니다. 20을 40과 비교한 다음 20과 40을 바꿉니다. 20을 30과 비교한 다음 20과 30을 바꿉니다. 하나의 움직임은 하나의 작업입니다. 6번의 비교는 6번의 연산입니다. 6개의 스왑은 6개의 작업입니다. 이 섹션에서는 13가지 작업을 제공합니다. 지금까지 총 49개의 작업이 있습니다(36 + 13 = 49). 결과는 다음과 같습니다.
20 30 40 50 60 70 80 | 10
인덱스 7에서 10으로 이동합니다. 10은 80과 비교되고 10과 80은 교환됩니다. 10을 70과 비교한 다음 10과 70을 바꿉니다. 10을 60과 비교한 다음 10과 60을 바꿉니다. 10을 50과 비교한 다음 10과 50을 바꿉니다. 10을 30과 비교한 다음 10과 40을 바꿉니다. 10을 30과 비교한 다음 10과 30을 바꿉니다. 10을 20과 비교한 다음 10과 20을 바꿉니다. 하나의 움직임은 하나의 작업입니다. 7번의 비교는 7번의 연산입니다. 7개의 스왑은 7개의 작업입니다. 이 섹션에서는 15가지 작업을 제공합니다. 지금까지 총 64개의 작업이 있습니다(49 + 15 = 64). 결과는 다음과 같습니다.
10 20 30 40 50 60 70 80 10 |
작업이 완료되었습니다! 64개의 작업이 참여했습니다.
64 = 8 x 8 = 8 둘
삽입 정렬의 시간 복잡도
삽입 정렬로 정렬할 요소가 n개 있는 경우 이전에 설명한 것처럼 가능한 최대 작업 수는 n2입니다. 삽입 정렬 시간 복잡도는 다음과 같습니다.
에 둘 )
이것은 Big-O 표기법을 사용합니다. Big-O 표기법은 대문자 O로 시작하고 그 뒤에 괄호가 옵니다. 괄호 안에는 가능한 최대 연산 수에 대한 표현식이 있습니다.
C 코딩
스캔을 시작할 때 첫 번째 요소는 위치를 변경할 수 없습니다. 프로그램은 기본적으로 다음과 같습니다.
#includevoid 삽입정렬 ( 정수 A [ ] , 정수 N ) {
~을 위한 ( 정수 나 = 0 ; 나 < N; 나는 ++ ) {
정수 j = 나;
동안 ( ㅏ [ 제이 ] < ㅏ [ 제이- 1 ] && 제이- 1 > = 0 ) {
정수 온도 = A [ 제이 ] ; ㅏ [ 제이 ] = 에이 [ 제이- 1 ] ; ㅏ [ 제이- 1 ] = 온도; // // 교환
제이--;
}
}
}
insertSort() 함수 정의는 설명된 대로 알고리즘을 사용합니다. while 루프의 조건에 유의하십시오. 이 프로그램에 적합한 C 주 함수는 다음과 같습니다.
{
정수 n = 8 ;
정수 A [ ] = { 오십 , 60 , 30 , 10 , 80 , 70 , 이십 , 40 } ;
삽입정렬 ( 에이, 엔 ) ;
~을 위한 ( 정수 나 = 0 ; 나 < N; 나는 ++ ) {
인쇄 ( '%나 ' , ㅏ [ 나 ] ) ;
}
인쇄 ( ' \N ' ) ;
반품 0 ;
}
결론
삽입 정렬의 시간 복잡도는 다음과 같습니다.
에 둘 )
독자는 최악의 경우 시간 복잡도, 평균 경우의 시간 복잡도 및 최상의 경우의 시간 복잡도에 대해 들어봤을 것입니다. 삽입 정렬 시간 복잡성의 이러한 변형은 당사 웹 사이트의 다음 기사에서 설명합니다.