삽입 정렬

삽입 정렬

삽입 정렬 애니메이션
클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O}$( ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})$ 비교$$ 및 스왑
베스트 케이스 공연	${\displaystyle O}$( ${\displaystyle n}$) ${\displaystyle O(n)}$ 비교$$, ${\displaystyle \mathrm{O}}$( 1${\displaystyle }$) ${\displaystyle$ O$(1)$스왑$$
평균 공연	${\displaystyle O}$( ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})$ 비교$$ 및 스왑
최악의 경우 공간 복잡성	${\displaystyle O}$( ${\displaystyle n}$) ${\displaystyle O(n)}$ 합계$$, ${\displaystyle \mathrm{O}}$( 1${\displaystyle }$) ${\displaystyle$ O$(1)$보조$$

삽입 정렬은 최종 정렬된 배열(또는 목록)을 한 번에 한 항목씩 작성하는 간단한 정렬 알고리즘이다. 퀵소트, 힙소트 또는 병합 정렬과 같은 고급 알고리즘보다 대형 목록에서 훨씬 덜 효율적이다. 그러나 삽입 정렬은 다음과 같은 몇 가지 이점을 제공한다.

• 간단한 구현: Jon Bentley는 3행 C 버전과 5행 최적화 버전을^[1] 표시
• 다른 2차 정렬 알고리즘과 마찬가지로 소규모 데이터 세트에 효율적임
• 선택 정렬 또는 버블 정렬과 같은 대부분의 다른 단순 2차(즉, O(n²) 알고리즘보다 실제가 더 효율적임
• 적응성, 즉, 이미 실질적으로 정렬된 데이터 세트에 효율적: 입력의 각 요소가 정렬된 위치에서 k 위치 이하인 경우 시간 복잡성은 O(kn)이다.
• 안정적(즉, 키가 같은 요소의 상대적 순서는 변경되지 않음)
• 인플레이스(in-place), 즉 일정한 양의 추가 메모리 공간 O(1)만 필요
• 온라인, 즉 수신 시 목록을 정렬할 수 있음

사람들이 수동으로 카드를 분류할 때, 대부분의 사람들은 삽입 분류와 비슷한 방법을 사용한다.^[2]

알고리즘.

삽입 정렬의 그래픽 예. 부분 정렬된 목록(검은색)은 처음에 목록의 첫 번째 요소만 포함한다. 각 반복마다 한 요소(빨간색)가 "아직 주문 여부를 확인하지 않음" 입력 데이터에서 제거되고 정렬된 목록에 삽입된다.

삽입 정렬은 반복되며, 각 반복마다 하나의 입력 요소를 소비하고, 정렬된 출력 목록을 증가시킨다. 반복할 때마다 삽입 정렬은 입력 데이터에서 한 요소를 제거하고 정렬된 목록 내에 속하는 위치를 찾아 거기에 삽입한다. 입력 요소가 남아 있지 않을 때까지 반복한다.

정렬은 일반적으로 배열을 반복하고 그 뒤에 정렬된 목록을 증가시킴으로써 내부로 수행된다. 각 배열 위치에서 정렬된 목록의 가장 큰 값( 우연히 그 옆에 있는, 이전의 배열 위치 확인됨)과 비교하여 그곳의 값을 점검한다. 크면 원소를 제자리에 두고 다음으로 이동한다. 크기가 작을 경우 정렬된 목록 내에서 올바른 위치를 찾고, 모든 큰 값을 위로 이동하여 공간을 만들고, 올바른 위치에 삽입한다.

k 반복 후 결과 배열은 첫 번째 k + 1 항목이 소트되는 속성("첫 번째 항목을 건너뛰기 때문에"+1")을 갖는다. 각 반복에서 입력의 첫 번째 남은 입력 항목은 제거되고 올바른 위치에서 결과에 삽입되어 결과를 확장한다.

된다

x보다 큰 각 원소를 x와 비교했을 때 오른쪽으로 복사한다.

배열에서 작동하는 가장 일반적인 삽입 정렬의 변형은 다음과 같이 설명할 수 있다.

1. 배열의 시작 부분에 정렬된 시퀀스에 값을 삽입하도록 설계된 Insert라는 함수가 있다고 가정해 보십시오. 시퀀스 끝에서 시작하여 새로운 원소에 적합한 위치가 발견될 때까지 각 원소를 오른쪽으로 한 자리씩 이동시키는 방식으로 작동한다. 함수는 배열에서 정렬된 시퀀스 직후에 저장된 값을 덮어쓰는 부작용이 있다.
2. 삽입 정렬을 수행하려면 배열의 맨 왼쪽 요소에서 시작하여 삽입을 호출하여 마주친 각 요소를 올바른 위치에 삽입하십시오. 요소가 삽입되는 순서는 이미 조사된 인덱스 집합의 배열 시작 부분에 저장된다. 각 삽입은 하나의 값, 즉 삽입되는 값을 덮어쓴다.

완전한 알고리즘의 유사성(phasocode)이 뒤따르며, 여기서 배열은 영(0) 기반이다.^[1]

i ← 1 while i < 길이(A) j while i while j while i while j > 0 and A[j-1] 교환 A[j]와 A[j-1] j ← j - 1 end while i + 1 end while end end end end end end end end. 

외부 루프는 첫 번째 요소를 제외한 모든 요소에 걸쳐 실행되며, 단일 요소 접두사가 있기 때문이다. A[0:1] 시시콜콜하게 분류되어 있어서, 첫 번째 불변은 i 항목 정렬은 처음부터 참이다. 내부 루프가 요소를 이동함 A[i] 정확한 위치에 도달하여 루프 후 첫 번째 i+1 원소가 정리되다 참고: and-시험 시 반드시 단락 평가를 사용해야 하며, 그렇지 않으면 시험 시 배열 한계 오차가 발생할 수 있음 j=0 그리고 그것은 평가하려고 노력한다. A[j-1] > A[j] (즉, 접근) A[-1] 실패하다

확장 후 swap 로서의 내부 운영. x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x (어디서) x 임시 변수임), 약간 더 빠른 버전으로 이동 가능 A[i] 한 번에 제자리에 배치하고 내측 루프 본체에서 하나의 할당만 수행한다.^[1]

i[j+1] x ← A[i] j ← i - 1인 동안 j >= 0과 a[j] x A[j+1] ← A[j] j j j - 1인 동안 a[j+1] x i[3] + 1인 동안 a[j] x i i + 1인 경우 

새로운 내부 루프는 원소를 오른쪽으로 이동하여 자리를 비운다. x = A[i].

알고리즘도 재귀적으로 구현할 수 있다. 재귀는 단지 외부 루프를 대체하여 자신을 호출하고 n이 0이 될 때까지 스택에 n의 더 작은 값을 연속적으로 저장한다. 여기서 함수는 n으로 시작하는 각 재귀 호출 후 코드를 실행하기 위해 콜 체인을 상승시킨다. n은 함수의 각 인스턴스가 이전 인스턴스로 되돌아갈 때 1씩 증가한다. 초기 통화는 insertSortR(A, length(A)-1)이 될 것이다.

함수 insertSortR(어레이 A, int n) 0 > 0 삽입SortR(A, n-1) x [ A[n] j ← n-1, j >= 0과 A[j] x A[j+1] ← A[j] j ← j-1은 기능 종료 시 종료되는 반면, A[j+1] x x x end은 종료된다. 

코드를 더 짧게 하지 않고, 실행 시간도 줄이지 않지만, 추가 메모리 소비량을 O(1)에서 O(N)로 증가시킨다(가장 깊은 재귀 수준에서 스택은 N 참조를 포함한다). A 배열(각각 변수 값 포함 n N에서 1까지).

최고, 최악의 경우 및 평균 사례

최상의 사례 입력은 이미 정렬된 배열이다. 이 경우 삽입 정렬은 선형 실행 시간(예: O(n))을 갖는다. 각 반복 동안 입력의 첫 번째 남아 있는 요소는 배열의 정렬된 하위섹션의 가장 오른쪽 요소와만 비교된다.

가장 간단한 최악의 경우 입력은 역순으로 정렬된 배열이다. 최악의 경우 입력의 집합은 각 원소가 그 이전의 원소 중 가장 작거나 두 번째로 작은 모든 배열로 구성된다. 이 경우 내측 루프의 모든 반복은 다음 요소를 삽입하기 전에 배열의 전체 정렬된 하위섹션을 스캔하고 이동시킨다. 이렇게 하면 삽입 정렬의 2차 실행 시간(즉, O(n²))을 얻을 수 있다.

평균적인 사례도 2차적이어서 ^[4]대형 배열 정렬에 삽입이 실용적이지 않다. 그러나 삽입 분류는 퀵소트보다 더 빠르게 매우 작은 배열을 정렬하기 위한 가장 빠른 알고리즘 중 하나이다. 실제로, 좋은 퀵소트 구현은 하위 문제로 발생할 때에도 특정 임계값보다 작은 배열에 삽입 종류를 사용한다. 정확한 임계값은 실험적으로 결정되어야 하며 기계에 따라 다르지만 공통적이다.너 10시 쯤에

예: 다음 표에는 시퀀스 {3, 7, 4, 9, 5, 2, 6, 1}을(를) 정렬하는 단계가 나와 있다. 각 단계에서 고려 중인 키가 밑줄 친다. 이전 단계에서 움직인 키(또는 가장 크지만 고려된 키)에는 별표가 표시되어 있다.

3  7  4  9  5  2  6  1 3* 7  4  9  5  2  6  1 3  7* 4  9  5  2  6  1 3  4* 7  9  5  2  6  1 3  4  7  9* 5  2  6  1 3  4  5* 7  9  2  6  1 2* 3  4  5  7  9  6  1 2  3  4  5  6* 7  9  1 1* 2  3  4  5  6  7  9 

기타 정렬 알고리즘과의 관계

삽입 정렬은 선택 정렬과 매우 유사하다. 선택 정렬에서와 같이 k가 배열을 통과한 후 첫 번째 k 요소는 정렬된 순서대로 정렬된다. 그러나 두 알고리즘의 근본적인 차이점은 삽입 정렬은 현재 키에서 거꾸로 스캔하는 반면 선택 정렬은 앞으로 스캔한다는 것이다. 이렇게 하면 첫 번째 k 요소가 정렬되지 않은 입력에서 가장 작은 k 요소가 되는 반면 삽입 정렬에서는 단순히 입력의 첫 번째 k 요소가 된다.

선택 정렬보다 삽입 정렬의 주요 장점은 선택 정렬이 항상 목록의 정렬되지 않은 부분에서 절대적으로 가장 작은 요소를 찾기 위해 남아 있는 모든 요소를 스캔해야 하는 반면 삽입 정렬은 k-th 요소보다 (k + 1)-st 요소가 클 때, 이 요소가 자주 참일 때(예: 입력 배열이 이미 정렬되어 있거나 부분적으로 정렬되어 있는 것처럼), 삽입 정렬은 선택 정렬에 비해 확실히 더 효율적이다. 평균적으로(k+1)-위 요소의 순위가 랜덤하다고 가정할 때 삽입 정렬은 이전 k 요소의 반을 비교 및 이동해야 하며, 이는 삽입 정렬이 평균적으로 선택 정렬의 절반만큼의 비교를 수행한다는 것을 의미한다.

최악의 경우(입력 배열 역방향 정렬 시) 삽입 정렬은 선택 정렬과 마찬가지로 많은 비교를 수행한다. 그러나 선택 정렬보다 삽입 정렬의 단점은 각 반복에서 (k + 1)-st 요소를 배열의 정렬된 부분에 삽입하려면 많은 요소 스왑이 필요한 반면 선택 정렬의 각 반복에는 단일 스왑만 필요하기 때문에 더 많은 쓰기가 필요하다는 것이다. 일반적으로 삽입 정렬은 배열 O(n²) 시간에 쓰지만 선택 정렬은 O(n) 시간만 쓴다. 이러한 이유로 EEPROM이나 플래시 메모리와 같이 메모리에 쓰는 것이 읽기보다 훨씬 더 비용이 많이 드는 경우에는 선택 종류를 선택하는 것이 더 바람직할 수 있다.

퀵소트 및 병합과 같은 일부 분할 및 변환 알고리즘이 대형 어레이의 삽입 종류를 능가하는 반면 삽입 정렬 또는 선택 정렬과 같은 비반복 정렬 알고리즘은 일반적으로 매우 작은 어레이(정확한 크기는 환경과 구현에 따라 다르지만 일반적으로 7~50개 요소 사이)에서 더 빠르다. 따라서 그러한 알고리즘의 구현에서 유용한 최적화는 어레이가 작은 크기로 분할되었을 때 보다 단순한 알고리즘을 사용하는 하이브리드 접근법이다.^[1]

변형

D.L. Shell은 알고리즘을 상당히 개선했다. 수정된 버전은 Shell sort라고 불린다. 정렬 알고리즘은 각 패스에서 감소하는 거리로 분리된 원소를 비교한다. 셸 정렬은 실제 작업에서 주행 시간이 확연히 개선되었으며, 두 가지 간단한 변형에는 O(n^3/2)와 O(n^4/3) 주행 시간이 필요하다.^[5][6]

예를 들어 참조에 의해 저장된 문자열 키나 인간 상호 작용(예: 나란히 표시된 쌍 중 하나를 선택하는 것)과 같이 비교 비용이 스왑 비용을 초과하는 경우, 이진 삽입 정렬을 사용하면 성능이 향상될 수 있다.^[7] 바이너리 삽입 정렬은 바이너리 검색을 사용하여 새 요소를 삽입할 올바른 위치를 결정하므로 최악의 경우 ⌈log₂ n⌉ 비교를 수행한다. 배열의 각 요소를 검색하여 삽입하면 O(n log n)가 된다.^[7] 각 삽입에 필요한 일련의 스왑 때문에 알고리즘 전체는 평균적으로 O(n²)의 실행 시간을 가진다.^[7]

여러 요소의 위치를 계산한 후 이동하면 스왑 횟수를 줄일 수 있다. 예를 들어, 두 요소의 목표 위치가 적절한 위치로 이동하기 전에 계산되는 경우, 무작위 데이터의 경우 스왑 수를 약 25% 줄일 수 있다. 극단적인 경우, 이 변형은 병합 분류와 유사하게 작동한다.

이진 병합 정렬이라는 이름의 변종은 32개 요소의 그룹을 정렬하기 위해 이진 삽입 정렬을 사용하고, 그 다음 병합 정렬을 사용하여 최종 정렬을 사용한다. 소형 데이터 세트의 삽입속도와 대형 데이터 세트의 병합속도를 결합한 것이다.^[8]

삽입할 때마다 일련의 스왑을 할 필요가 없도록, 입력은 링크된 목록에 저장될 수 있어 목록의 위치가 알려졌을 때 일정한 시간 내에 요소들을 목록 안으로 또는 밖으로 분할할 수 있다. 그러나 링크된 목록을 검색하려면 원하는 위치에 대한 링크를 순차적으로 따라야 한다. 링크된 목록은 임의의 액세스 권한을 가지지 않으므로 바이너리 검색과 같은 더 빠른 방법을 사용할 수 없다. 따라서 검색에 필요한 실행시간은 O(n), 정렬시간은 O(n²)이다. 보다 정교한 데이터 구조(예: 힙 트리 또는 이진 트리)를 사용할 경우 검색 및 삽입에 필요한 시간이 크게 단축될 수 있다. 이것이 힙 정렬과 이진 트리 정렬의 본질이다.

2006년에 Bender, Martin Farach-Colton, Mosteiro는 라이브러리 정렬 또는 개핑된 삽입 정렬이라고 하는 새로운 변형 삽입 유형을 발표하여 사용하지 않는 소수의 공간(즉, "갑")을 어레이 전체에 분산시켰다. 이점은 삽입은 간격에 도달할 때까지 요소들을 이동시킬 필요가 있다는 것이다. 저자들은 이 정렬 알고리즘이 O(n log n) 시간에 높은 확률로 실행된다는 것을 보여준다.^[9]

스킵 리스트를 사용할 경우 삽입 시간을 O(log n)로 낮추고, 스킵 리스트가 링크된 리스트 구조에서 구현되기 때문에 스왑이 필요하지 않다. 삽입을 위한 최종 실행 시간은 O(n log n)가 될 것이다.

목록 삽입 정렬은 삽입 정렬의 변형이다. 그것은 움직임의 수를 줄인다.^{[citation needed]}

C에 삽입 정렬 코드 나열

항목이 링크된 목록에 저장되면 O(1) 추가 공간으로 목록을 정렬할 수 있다. 알고리즘은 처음에 비어 있는 목록(따라서 사소한 정렬)으로 시작한다. 입력 항목은 한 번에 하나씩 목록에서 꺼낸 다음 정렬된 목록의 적절한 위치에 삽입된다. 입력 목록이 비어 있으면 정렬된 목록에 원하는 결과가 있다.

구조상의 목록 * SortList1(구조상의 목록 * pList)  {     // 0 또는 목록에 있는 요소 하나     만일 (pList == NULL    pList->pNext == NULL)         돌아오다 pList;     // 헤드는 결과 정렬된 목록의 첫 번째 요소     구조상의 목록 * 머리 = NULL;     하는 동안에 (pList != NULL) {         구조상의 목록 * 현재의 = pList;         pList = pList->pNext;         만일 (머리 == NULL    현재의->iValue < 머리->iValue) {             // 정렬된 목록의 머리글에 삽입             // 또는 빈 정렬 목록의 첫 번째 요소로서             현재의->pNext = 머리;             머리 = 현재의;         } 다른 {             // 정렬되지 않은 목록에서 현재 요소를 올바른 위치에 삽입             구조상의 목록 * p = 머리;             하는 동안에 (p != NULL) {                 만일 (p->pNext == NULL    // 정렬된 목록의 마지막 요소                     현재의->iValue < p->pNext->iValue) // 리스트의 중간                 {                     // 정렬된 목록의 중간 또는 마지막 요소로 삽입                     현재의->pNext = p->pNext;                     p->pNext = 현재의;                     부숴뜨리다; // 완료                 }                 p = p->pNext;             }         }     }     돌아오다 머리; } 

아래 알고리즘은 정렬된 목록에 삽입하기 위해 후행 포인터를^[10] 사용한다. 더 단순한 재귀적 방법은 (스플라이싱이 아닌) 매번 목록을 재구성하고 O(n) 스택 공간을 사용할 수 있다.

구조상의 목록 {   구조상의 목록 * pNext;   인트로           iValue; };  구조상의 목록 * 정렬 목록(구조상의 목록 * pList) {   // 0 또는 목록에 있는 요소 하나   만일 (!pList    !pList->pNext)       돌아오다 pList;    /* 빈 리스트에서 정렬된 어레이를 빌드 */   구조상의 목록 * 모듬된 = NULL;    /* 입력 목록에서 항목을 하나씩 비워 */   하는 동안에 (pList != NULL) {       /* 머리 기억 */       구조상의 목록 *   phead  = pList;       /* 효율적인 스플라이스를 위한 후행 포인터 */       구조상의 목록 ** ppTrail = &모듬된;        /* pop head off list       pList = pList->pNext;        /* 헤드를 올바른 위치에 정렬된 목록으로 연결 */       하는 동안에 (!(*ppTrail == NULL    phead->iValue < (*ppTrail)->iValue)) { /* 머리는 여기 있는 건가? */           /* no - 목록 아래로 계속 */           ppTrail = &(*ppTrail)->pNext;       }        phead->pNext = *ppTrail;       *ppTrail = phead;   }    돌아오다 모듬된; } 

참조

추가 읽기

• Knuth, Donald (1998), "5.2.1: Sorting by Insertion", The Art of Computer Programming, vol. 3. Sorting and Searching (second ed.), Addison-Wesley, pp. 80–105, ISBN 0-201-89685-0.

외부 링크

Wikibook 알고리즘 구현에는 다음과 같은 주제의 페이지가 있다. 삽입 정렬

Wikimedia Commons에는 삽입 정렬과 관련된 미디어가 있다.

• 애니메이션 정렬 알고리즘: 웨이백 머신에서 삽입 정렬(2015년 3월 8일 자료) – 그래픽 시연
• Adamovsky, John Paul, Binary Insertion Sort – Scoreboard – Complete Investigation and C Implementation, Pathcom.
• Insertion Sort – a comparison with other O(n²) sorting algorithms, UK: Core war.
• Insertion sort (C) (wiki), LiteratePrograms – C 및 기타 여러 프로그래밍 언어로 삽입 정렬 구현