병합 삽입 정렬

컴퓨터 공학에서, 병합 삽입 분류 또는 포드-존슨 알고리즘은 L. R. 포드 주니어와 셀머 M. 존슨에 의해 1959년에 출판된 비교 분류 알고리즘이다.^[1][2][3][4]이전에 가장 잘 알려진 알고리즘,^[5] 이진 삽입 정렬 및 병합 정렬보다 최악의 경우 비교를 적게 사용하며,^[1] 20년 동안 가장 적게 알려진 비교를 가진 정렬 알고리즘이었다.실제적인 의미는 아니지만 최소 비교 횟수로 분류하는 문제와 관련하여 이론적 관심사로 남아 있다.^[3]같은 알고리즘은 스타니스와프 트라이부바와와 크젠 핑에 의해서도 독자적으로 발견되었을지도 모른다.^[4]

알고리즘.

병합 삽입 정렬은 $n{\displaystyle }$ ${\displaystyle n}$ 요소의$$$$ 입력 $X{\displaystyle }$ ${\displaystyle X}$에서 다음 단계를 수행하십시오.^[6]

1. $X{\displaystyle }$ ${\displaystyle X}$의 요소를 ${\displaystyle \mathrm{임의}}$로 $\lfloor {\displaystyle }$ n${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor }$ 쌍의$$ 원소로$$ 그룹화하여, 원소의 수가 홀수일 경우 하나의 원소가 손상되지 않도록 하십시오.
2. ${\displaystyle \mathrm{pair}}$ n /${\displaystyle 2\mathrm{}}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor n/2\rfloor }$을(를) 쌍당 하나씩 비교하여 각 쌍의 두 요소 중 더 큰 요소를 확인하십시오.
3. 각 쌍에서 더$$ 큰 원소를 $\lfloor {\displaystyle }$ ${\displaystyle n}$/ ${\displaystyle 2\mathrm{}}$⌋ ${\displaystyle \lfloor }$ 재귀적으로 정렬하여 ${\displaystyle \mathrm{입력}}$ 요소의 $\lfloor {\displaystyle }$ n${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor n/2\rfloor }$의 정렬된 시퀀스 $S{\displaystyle }$ ${\\displaystystylease S}$을 오름차순으로 만드십시오.
4. $S{\displaystyle }$ ${\$$displaystyle S}$의 첫 번째 및 가장 작은 요소와 쌍을 이룬 요소를$$ S ${\$$displaystyle S}$의 시작 부분에 삽입하십시오$.$
5. 아래에서 특별히 선택한 ${\displaystyle 삽입\mathrm{}}$ 순서와 $함께{\displaystyle }$ X${\displaystyle }$∖ ${\displaystyle S}$${\$$displaystyle \lceil n/$2$\rceil -1$}의 나머지 $⌈$ $/2\rceil$ -1} 요소를$$ 한 번에 하나씩$$$S{\displaystyle }$ ${\displaystyle$S}에$$ 삽입하십시오${\displaystyle .}$각 $요소$가$$삽입되어야 하는 위치를 $결정$하려면 S {\displaystyle $S}($아래 설명 참조)의 하위 항목에서 이진 검색을 사용하십시오.

이 $알고리즘$은 검색되는 부속품의 길이가 2의 전력보다 1보다 작을 때 S ${\displaystyle S}$에 요소를 삽입하는 데 사용되는 이진 검색이 (최악의 경우 분석의 관점에서) 가장 효율적이라는$$ 점을 이용하기 위해 설계되었다.이는 이러한 길이에 대해 검색의 모든 결과는 서로 동일한 수의 비교를 사용하기 때문이다.^[1]이러한 길이를 생성하는 삽입 순서를 선택하려면 위의 개요 4단계(남은$$ 요소를 삽입하기 전에) 뒤에 정렬된 $시퀀스{\displaystyle }$ S ${\displaystyle S}$을(를) 고려하십시오. $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$는 이 정렬된 시퀀스의 $i{\displaystyle }$ ${\displaystyle i}$ 요소를$$ 나타내도록$$ 하십시오.그러므로,

${\displaystyle S=(x_{1},x_{2},x_{3},\dots )}$

여기서 $i{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 3}$ ${\displaystyle i\geq$ 3$}$이(가) 있는 각 요소 x ${\displaystyle i_{}}$ ${\$$displaystyle x_{i}$은(는) 아직 삽입되지 않은 y< x i$>$와 쌍을 이룬다$$.(${\displaystyle {x1\mathrm{}}_{}}$ ${\$ $y_{1},$ $y$ 2 ${\$${$1$}:{$$1},$ ${\displaystyle x_{}}$ $2{\displaystyle {}_{}}$ ${\$displaystyle $x_$${$2}}개가 서로 쌍으로 이루어졌기$$ 때문에$$ y ${\displaystyle {1\mathrm{}}_{}}$ ${\$displaystyle $x_${1} 또는 y ${\displaystyle {2\mathrm{}}_{}}$ {\$displaystystylem$ x_${$2}}$개$의 요소가 없다.)$n{\displaystyle }$ ${\displaystyle n}$이(가) 홀수인 경우, ${\displaystyle {나머지}_{}}$ 손상되지 않은 요소도 쌍체 요소의 인덱스보다 큰$$ $i$ ${\displaystyle y_$${i$$}$로 $번호$가 매겨져야 한다.그러면 위의 개요의 마지막 단계를 다음과 같은 단계로 확장할 수 있다.^[1][2][3][4]

• 삽입되지 않은 요소 $y{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$를 연속$$ 인덱스가 있는 그룹으로 분할하십시오.첫 번째 그룹에는$$ ${\displaystyle {y\mathrm{}}_{}}$ 3 ${\$와 ${\displaystyle {y\mathrm{}}_{}}$ $4{\displaystyle {}_{}}$ ${\$ 두 개의 요소가 있으며, 인접한 두 그룹마다 크기 합이 두 개의 힘의 순서를 형성한다.따라서, 집단의 크기는: 2, 2, 6, 10, 22, 42, ...
• 삽입되지 않은 요소를 그룹별로 정렬(소형 인덱스부터 대형 인덱스까지)하되, 각 그룹 내에서는 대형 인덱스에서 소형 인덱스까지 정렬한다.따라서 순서는 다음과 같이 된다.

${\displaystyle y_{4},y_{3},y_{6},y_{5},y_{12},y_{11},y_{10},y_{9},y_{8},y_{7},y_{22},y_{21}\cs}$

• ${\displaystyle {이}_{}}$ 순서를 사용하여 y i ${\$ 요소를 $S{\displaystyle }$ ${\displaystyle Y_${$i$$}$에 삽입하십시오$.$ 각 ${\displaystyle {요소}_{}}$ y ${\$에 대해$,$ $S{\displaystyle }$ ${\displaystyle S}$의 $시작$부터 x ${\displaystyle i_{}}$ ${\$까지 이진 검색을 사용하여$$ $}$를 삽입할 위치를 결정하십시오.$tyle y_{i}}}$.

분석

$Let{\displaystyle }$ C${\displaystyle }$( ${\displaystyle n}$) ${\displaystyle C(n)}$은(는) $n{\displaystyle }$ ${\displaystyle n}$ 요소를$$ 정렬할 때 최악의 경우 병합 삽입 정렬이 수행하는 비교 수를 나타낸다.이 비교 횟수는 다음과 같은 세 항의 합으로 나눌 수 있다.

• ${\displaystyle \mathrm{항목}}$ 쌍 간의${\displaystyle 2\mathrm{}}$ n /${\displaystyle }$2$$ {\$displaystyle \lfloor$ n$/2\orloor }$ 비교$$,
• ${\displaystyle C}$ (${\displaystyle \lfloor }$ ${\displaystyle n}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rfloor }$) ${\displaystyle$ C$(\lfloor n/2\rfloor )}$ 재귀 호출에 대한 비교$$ 및
• 나머지 요소를 삽입하는 데 사용되는 이항 삽입에 대한 일부 비교 수입니다.

세 번째 항에서, 첫 번째 그룹의 원소에 대한 최악의 경우 비교 횟수는 두 가지인데, 각각 길이가 최대 $3인$ S ${\displaystyle S}$에 삽입되기 때문이다.$먼저$ $y{\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$${4}}$을(를) 3개 요소 부분$x1, x$ ${\displaystyle {2\mathrm{}}_{}}$,$x$)에 삽입한다$.$Then, ${\displaystyle y_{3}}$ is inserted into some permutation of the three-element subsequence ${\displaystyle (x_{1},x_{2},y_{4})}$, or in some cases into the two-element subsequence ${\displaystyle (x_{1},x_{2})}$. Similarly, the elements ${\displaysty$$두$ 번째 그룹의$$ $le$y_{$6}$와 y 5 ${\$y_${5$}}는$$ 각각 3가지 비교를 사용하여 최대 7개까지 길이로 배열되어 삽입된다.왜냐하면 각각의 길이가 연속으로 말미암아, 대부분의 2에 삽입되면 더 일반적으로, 비교의 i의 요소에 대한 최악의 번호는 나는 + 1{\displaystyle를 i+1}, th그룹{\displaystyle 나는}나는 및 1− 1{\displaystyle 2^{i+1}-1}.[1][2][3][4]까지 가산 수 비교할 때 사용하는 모든 요소와 해결하자는 거죠.그 결과ingreative responsion, 이 분석은 공식을^[7] $제공$하는 C${\displaystyle }$(${\displaystyle n}$) ${\displaystyle C(n)}$의 값을 계산하는 데 사용될 수 있다$.$

${\displaystyle C(n)=\sum _{i=1}^{n}\왼쪽\lceil \log _{2}{\frac {3i}{4}}\right\rceil \cessil \reason n\log _{2}n-1.415n}$

아니면,^[8] 폐쇄적인 형태로

${\displaystyle C(n)=n{\biggl \lceil }\log _{2}{\frac {3n}{4}}{\biggr \rceil }-{\biggl \lfloor }{\frac {2^{\lfloor \log _{2}6n\rfloor }}{3}}{\biggr \rfloor }+{\biggl \lfloor }{\frac {\log _{2}6n}{2}}{\biggr \rfloor }.}$

$n{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$…$${\$displaystyle n=1,2,\dots}$의 경우 비교$$ 횟수는 다음과 같다^[1].

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... (OEIS에서 연속 A001768)

기타 비교 유형과의 관계

알고리즘은 재귀 호출 전에 수행하는 초기 비교(임의적인 항목 준비 및 각 쌍 비교)가 병합 정렬의 초기 비교와 동일한 반면, 재귀 호출 후 수행하는 비교(이항 검색을 사용하여 요소를 하나씩 a에 삽입)는 것이기 때문에 병합 삽입 정렬이라고 불린다.정렬된 목록) 삽입 정렬과 같은 원리를 따른다.그런 의미에서 병합 정렬과 삽입 정렬을 모두 결합한 하이브리드 알고리즘이다.^[9]

작은 입력($최대{\displaystyle }$ n${\displaystyle }$= ${\displaystyle 11}$ ${\displaystyle n=11$의 경우 비교 횟수는 $\lceil {\displaystyle }$ ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle n!}$ ${\displaystyle \rceil }$ n ${\displaystyle \mathrm{로그}}$ 2${\displaystyle {}_{}2}$ -${\displaystyle }$1${\displaystyle \mathrm{.}\mathrm{443n}}$ ${\displaystyle \lceil$ \$log _{2$}n$!$$\rceil \cHB _{2}n-1.443n$ 그러나 입력 값이 클 경우 병합-삽입 알고리즘에 의한 비교 횟수가 이 하한보다 크다.또한 병합 삽입 정렬은 최악의 경우 이진 삽입 정렬 또는 병합 정렬에 의해 수행된 비교를 계산하는 정렬 번호보다 더 적은 비교를 수행한다.$정렬{\displaystyle }$ 번호는 n ${\displaystyle \log }$ 2 -${\displaystyle {}_{}}$n${\displaystyle }$-${\displaystyle 0}$.${\displaystyle \mathrm{915}}$ n$${\$displaystyle$n\$log _{$2}$n-0.915n$$\}$과 ${\displaystyle n_{}}$ ${\displaystyle {log\mathrm{}}_{}}$2 ${\displaystyle \log }$2$$n - n {\$displaystyn\log _{$2}n-n} 사이에서 변동하며, 선행 항은 동일하지만 저차 선형 항에서는 더 나쁜 상수 요인이다.^[1]

때마다 n22{20\leq n\leq 22\displaystyle}≤며 20년 동안 가장 적은 비교와 ≤ 46{\displaystyle n\leq 46}.[10][11]을 알고 있다 15{\displaystyle n\leq 15}또는 20≤ n≤, merge-insertion n{n\displaystyle}항목에 대한 최소 가능한 비교와 Merge-insertion는 정렬 알고리즘입니다. 것이었습니다모든 입력 길이에 대해 알려진 비교가 가장 적은 정렬 알고리즘.그러나 1979년 Glenn Manacher는 다른 분류 알고리즘을 발표했는데, 이 알고리즘은 많은 입력값을 위해 비교를 더 적게 사용했다.^[3][5]모든 $n{\displaystyle }$ ${\displaystyle n$에 대해 정렬에 정확히 얼마나 많은 비교가 필요한지는 아직 정확히 알려지지 않았지만 Manacher의 알고리즘과 이후 기록을 깨는 정렬 알고리즘은 모두 병합 삽입 정렬 아이디어의 수정을 사용했다.^[3]

참조