블록 정렬

Block sort
블록 정렬 압축과 혼동하지 마십시오.
블록 정렬
Block sort with numbers 1 to 16 (thumb).gif
번호 1부터 16까지의 정렬을 안정적으로 차단하십시오.
16개로 구성된 정렬 그룹을 삽입하고, 2개의 내부 버퍼를 추출하고, A 블록(각각 크기가 16 = 4인)에 태그를 지정한 다음, A 블록을 B로 롤링하고, 이를 로컬로 병합하고, 두 번째 버퍼를 정렬하고, 버퍼를 재배포한다.
클래스정렬 알고리즘
데이터 구조배열
최악의 경우 공연O(n log n)
베스트 케이스 공연O(n)
평균 공연O(n log n)
최악의 경우 공간 복잡성O(1)

블록 정렬 또는 블록 병합 정렬은 삽입 정렬과 최소 두 개의 병합 작업을 결합하여 O(n log n)의 안정적인 정렬에 도달하는 정렬 알고리즘이다.A와 B라는 두 개의 정렬된 리스트를 병합하는 것은 A를 균일한 크기의 블록으로 쪼개고, 각 A 블록을 B에 특수 규칙에 따라 삽입하며, AB 쌍을 병합하는 것과 같다는 관측에서 그 이름을 얻는다.

제자리 합병을 위한 O(log n) 알고리즘은 2008년 김폭손과 아르네 쿠츠너가 제안하였다.[1]

개요

블록 정렬의 외부 루프는 하위 배열 쌍인 A와 B를 각 레벨의 하위 배열 쌍이 1, 2, 4, 8, 16 등의 크기로 병합하는 상향 병합 정렬과 동일하다. 여기서 결합된 두 하위 선이 배열 자체일 때까지.

오히려 합병보다 A와 B민족의 전통 방식과,block-based 병합 알고리즘 크기의 개별 블록으로 √A(블록의√A 수에서도 결과)[2]를 삽입한 구분 각 A를 B로 블록이 각 블록의 첫번째 값 또는(≤)B값으로 즉시 그것을 쫓고 그 지역적으로 각 블록이 합쳐진다 같은 경우.wi그것과 다음 A 블록 사이의 모든 B 값.

병합에는 여전히 A 블록을 병합할 수 있을 만큼 큰 별도의 버퍼가 필요하므로, 어레이 내의 두 영역은 이러한 목적으로 예약된다(내부 버퍼라고도 함).[3]따라서 처음 두 개의 A 블록은 A 내에서 각 값의 첫 번째 인스턴스를 포함하도록 수정되며, 이러한 블록의 원래 내용은 필요한 경우 위로 이동된다.그런 다음 나머지 A 블록을 B에 삽입하고 두 버퍼 중 하나를 스왑 공간으로 사용하여 병합한다.이 프로세스는 버퍼의 값을 다시 정렬하게 한다.

모든 A 및 B 하위 어레이의 A 및 B 블록이 해당 수준의 병합 정렬에 대해 병합된 후에는 해당 버퍼의 값을 정렬하여 원래 순서를 복원해야 하므로 삽입 정렬이 적용되어야 한다.그런 다음 버퍼의 값은 배열 내에서 첫 번째 정렬 위치로 다시 분배된다.이 프로세스는 배열이 안정적으로 정렬되는 외부 상향 병합 정렬의 각 수준에 대해 반복된다.

알고리즘.

코드 예에서는 다음과 같은 연산자를 사용한다.

비트 와이즈 OR
>> 우회전하다
% 모둘로
++++= 증분하다
[x, y) ≥ x와 < y의 범위
범위 range.end – range.start
배열[i]하다 i번째 배열 항목

또한 블록 정렬은 전체 알고리즘의 일부로 다음과 같은 작업에 의존한다.

  • 스왑: 배열에서 두 값의 위치를 교환한다.
  • 블록 스왑: 배열 내에서 다른 범위의 값과 값의 범위를 교환한다.
  • 바이너리 검색: 배열이 정렬되었다고 가정하여 현재 검색 범위의 중간 값을 확인한 다음 값이 작으면 하한 범위를, 값이 크면 상한 범위를 확인하십시오.블록 정렬은 정렬된 배열에서 값을 삽입할 첫 번째 위치를 찾는 변종과 마지막 위치를 찾는 변종 두 가지를 사용한다.
  • 선형 검색: 찾을 때까지 모든 요소를 순서대로 확인하여 배열에서 특정 값을 찾으십시오.
  • 삽입 정렬: 배열의 각 항목에 대해 뒤로 반복하여 삽입할 위치를 찾은 다음 해당 위치에 삽입하십시오.
  • 배열 회전: 배열의 항목을 몇 개의 공백으로 왼쪽 또는 오른쪽으로 이동하며 가장자리의 값은 반대쪽으로 감싼다.회전은 세 번의 반전으로 실행될 수 있다.[4]
회전(어레이, 양, 범위) 후진(어레이, 범위) 후진(어레이, [range.start, range.start + 양)후진(어레이, [range.start + 양, range.end)]
  • 플로어 파워 2: 다음 파워 2로 값을 플로어한다.따라서 63은 32가 되고 64는 64가 된다.[5]
FloorPowerOfTwo(x) x = x (x > > 1) x = x (x > > > 2) x = x (x >> 4) x = (x > 8) x = x (x > 16) 만약 (이것이 64비트 시스템이라면) x = (x > 32) return x - (x > 1)

외부 루프

앞에서 설명한 바와 같이 블록 분류의 외부 루프는 상향식 병합 분류와 동일하다.그러나, 그것은 각각을 보장하는 변종으로부터 이익을 얻는다.A, 그리고B하위 배열은 한 항목 내에서 동일한 크기:

BlockSort(배열)power_of_two)FloorPowerOfTwo(array.size)규모)array.size/power_of_two을 끓여1.0≤ 규모<>(;< 합병;power_of_two, += 16합병=0합병)시작 한번에 2.0//삽입 정렬 16–31 항목)합병*규모 엔드 탭 + 16*규모 InsertionSort(배열,-LSB- 시작, 끝))시작한다.            항의라도만약(array[끝 − 1]<>array[시작하])(;< 합병;power_of_two,+=길이*2합병=0합병)출발을 위한 R(길이=16;길이 <, power_of_two, 길이+=길이))*규모 중반)(+길이 합병)*규모 엔드 탭(+길이*2합병)*규모 통합한다.                 그 // 두 범위는 역순으로 되어 있으므로, 회전은 (array[mid - 1] > 어레이[mid]인 경우 Rotate (array, mid - start, [start, end])를 합치기에 충분하다.병합(array, A = [start, middle, middle), B = [mid, end]) // 그렇지 않으면 범위가 이미 올바르게 정렬되어 있음

척도계수를 분수로 표시하여 고정점 산술도 사용할 수 있다.integer_part + numerator/denominator:

Power_of_two)FloorPowerOfTwo(array.size)분모)power_of_two/16 numerator_step array.size =%분모integer_step=floor(array.size/denominator)// 한번에 삽입 정렬 16–31 항목는 동안(integer_step<>array.size)integer_part= 분자)0인 반면(integer_part<>array.size)//다. 그 A와 B start의 범위 = 정수_part 정수_part += 정수_step 분자 += 분자(숫자 ≥분모) -=분모 정수_part++ mid = 정수_part += 정수_step분자 += 분자 = if (분모 if분모) 분자 -=분모 정수_part++ end = 정수_part (array[end - 1] < 배열[start])]회전(배열, 중간 시작, [시작, 끝]) 또는 (배열 [중간] >배열 [중간])병합(array, A = [start, mid, mid, end)) 정수_step += 정수_step_step_step +=분자_step_step_step +=분모_step++인 경우

버퍼 추출

블록 정렬에 대한 버퍼 추출 프로세스.

병합 단계의 각 레벨에 필요한 내부 버퍼 2개는 각 값의 처음 2√A 인스턴스를 1개 이내로 이동하여 생성된다.A의 시작에 이르기 까지 아열대하다A첫째로, 원소들을 반복한다.A그리고 필요한 고유 값을 카운트다운한 다음 어레이 회전을 적용하여 해당 고유 값을 처음부터 다시 이동시킨다.[6]A에 두 개의 버퍼를 채울 만큼 고유한 값이 없는 경우(각각 크기 valuesA)B또한 사용될 수 있다.이 경우 각 값의 마지막 인스턴스를 끝 부분으로 이동시킨다.B, 의 그 부분과 함께B병합 중에 포함되지 않음. 

반면 (1968_step <array.size) block_size = √integer_step buffer_size = 정수_step/block_size + 1 [각각 'size_size' 크기의 버퍼 2개]

만약B또한 충분한 고유 값을 포함하지 않고, 찾을 수 있는 가장 많은 고유 값을 꺼낸 다음, 그 크기를 조정한다.A, 그리고B결과의 수가 다음과 같이 차단된다.A블록은 버퍼에 대해 꺼낸 고유 항목의 수보다 작거나 같다.이 경우 한 개의 버퍼만 사용되며, 두 번째 버퍼는 존재하지 않는다. 

buffer_size = [발견된 고유값의 수] block_size = 정수_step/buffer_size + 1 정수_part = 숫자 = 0인 동안 [integer_part <array.size] [A와 B의 범위를 가져오기] [버퍼가 사용하는 범위를 포함하지 않도록 조정]

A 블록 태그

태그 지정:A첫 번째 내부 버퍼의 값을 사용하는 블록.첫째,A막다른 골목에서B블록의 크기가 고르지 않다

한두 개의 내부 버퍼가 생성되면 각 버퍼를 병합하기 시작한다.A, 그리고B이 수준의 병합 정렬에 대한 하위 배열.이를 위해 A와 B 서브어레이를 각각 이전 단계에서 계산한 크기의 균일한 크기의 블록으로 나눈다.A막다른 골목에서B블록은 필요에 따라 크기가 일정하지 않다.그런 다음 크기가 균일한 A 블록을 각각 반복하고 두 개의 내부 버퍼 중 첫 번째 값에서 두 번째 값을 해당하는 값으로 스왑한다.이것은 블록에 태깅을 하는 것으로 알려져 있다. 

나머지 한 블록, 끓여서 firstA은 고르지 않게 크기 처음 한 블록을 끓여blockA의 범위 blockA--LSB- A.start, A.end)firstA-경우 A.start, A.start+blockA%block_size) 끓여스왑이 둘째 값의 각 A블록과 가치의 buffer1에(지수=0indexA)firstA.end 1+;indexA<>blockA.end,indexA += block_size)스왑(배열용.늠름한 남자fer1.start + 인덱스, 어레이[indexA]] 인덱스++ lastA = firstA 블록B = [B.start, B.start + 최소(block_size, B ) 블록A.start += firstA

롤앤드롭

B블록 사이로 A블록 두 개가 굴러간다.첫 번째 A 블록이 뒤로 떨어지면 불균일하게 크기가 큰 A 블록이 그 블록을 따르는 B 값과 국소적으로 병합된다.

이러한 방식으로 A 블록을 정의하고 태그를 지정한 후 첫 번째 균일하게 크기가 지정된 A 블록을 다음 B 블록과 교환하여 A 블록을 B 블록으로 굴린다.이 프로세스는 태그 값이 가장 작은 A 블록의 첫 번째 값이 방금 A 블록과 스왑된 B 블록의 마지막 값보다 작거나 같을 때까지 반복된다.

이때 최소 A 블록(태그 값이 가장 작은 A 블록)을 롤링 A 블록의 시작으로 스왑하고 태그가 지정된 값을 첫 번째 버퍼에서 원래 값으로 복원한다.이것은 더 이상 남은 A블록과 함께 굴려지지 않기 때문에 블록을 뒤로 떨어뜨리는 것으로 알려져 있다.그런 다음 A 블록을 이전 B 블록에 삽입하고, 먼저 B에 대한 이진 검색을 사용하여 A의 첫 번째 값이 B의 해당 인덱스 값보다 작거나 같은 인덱스를 찾은 다음, A를 해당 인덱스에서 B로 회전시킴으로써 A 블록을 이전 B 블록에 삽입한다. 

minA = blockA.start    indexA = 0       while (true)        // if there's a previous B block and the first value of the minimum A block is ≤ // the last value of the previous B block, then drop that minimum A block behind. // or if there are no B blocks left then keep dropping the remaining A blocks. if (( lastB  > 0 and array[lastB.end - 1] ≥ array[minA]) or  blockB  = 0)            // figure out where to split the previous B block, and rotate it at the split            B_split = BinaryFirst(array, array[minA], lastB)            B_remaining = lastB.end - B_split                       // swap the minimum A block to the beginning of the rolling A blocks BlockSwap(array, blockA.start, minA,block_size)                       // restore the second value for the A block Swap(array[blockA.start + 1], array[buffer1.start + indexA])            indexA++                       // rotate the A block into the previous B block Rotate(array, blockA.start - B_split, [B_split, blockA.start + block_size))                       // locally merge the p만약(buffer2>0)MergeInternal(배열, lastA, -LSB- lastA.end, B_split), buffer2) 다른 MergeInPlace(배열, lastA, -LSB- lastA.end, B_split)) 끓여Revious는 다음 B값을 가진 블록, 스왑 공간(그게 존재하는지)두번째 내부 버퍼를 사용하여, 끓여의 남아 있는 A블록의 범위를 업데이트 //알몬드LastA = [blockA.start - B_remaining, BlockA.start - B_remain + block_size] lastB = [lastA.end, lastA.end + B_remain] // A 블록이 더 이상 남아 있지 않으면 이 단계는 BlockA.start = Blocksize +_size로 끝난다.만약(blockA)0)방학 minA[새로 생긴 A블록 최소](아래 참조) 다른 북파 l. 만약(blockB<>block_size)//에 남은 A블록 이전에, 한 회전 Rotate(배열, blockB.start-blockA.start,[blockA.start, blockB.end)를 사용하여)은 고르지 않게 크기로 되어 있는 마지막 B블록, 끓여astB = [blockA.start, blockA.start +  blockB )            blockA.start +=  blockB             blockA.end +=  blockB             minA +=  blockB             blockB.end = blockB.start        else // roll the leftmost A block to the end by swapping it with the next B block BlockSwap(array, blockA.start, blockB.start, block_size)            lastB = [blockA.start, blockA.start + b.size) minA = blockA.end blockA.start +=block_size blockA.end +=block_size // 이 값은 최소값(blockB.end + block_size, b.end) //에 해당하지만 잠재력이 있다. overflow if (blockB.end > B.end - block_size)                blockB.end = B.end            else                blockB.end += block_size       // merge the last A block with the remaining B values if ( buffer2  > 0)        MergeInternal(array, lastA, [lastA.end, B.end), buffer2)    else MergeInPlace(array, lastA, [lastA.end, B.end))

이 단계에서 적용할 수 있는 한 가지 최적화는 플로팅 홀 기법이다.[7]최소 A 블록이 뒤로 떨어져서 이전 B 블록으로 회전해야 할 때, 그 이후에 그것의 내용이 로컬 병합에 대한 두 번째 내부 버퍼로 교환되는 경우, 사전에 A 블록을 버퍼와 교환하는 것이 더 빠를 것이며, 그 버퍼의 콘텐츠가 어떤 질서를 유지할 필요가 없다는 사실을 이용하기 위해서일 것이다.따라서 두 번째 버퍼(블록 스왑 전 A 블록)를 위치 색인에서 이전 B 블록으로 회전시키는 대신, 인덱스 후 B 블록의 값은 단순히 버퍼의 마지막 항목과 스와핑되는 블록을 차단할 수 있다.

이 경우의 부유홀은 배열을 중심으로 떠다니는 제2의 내부 완충기의 내용을 말하며, 품목이 질서를 유지할 필요가 없다는 의미에서 구멍 역할을 한다.

로컬 병합

일단 A 블록이 B 블록으로 회전되면, 이전 A 블록은 그 블록을 따르는 B 값과 병합되어 두 번째 버퍼를 스왑 공간으로 사용한다.첫 번째 A 블록이 뒤에 떨어졌을 때, 이는 시작점에서 불균일하게 크기가 큰 A 블록을 가리킨다. 두 번째 A 블록이 뒤에 떨어졌을 때 첫 번째 A 블록 등을 의미한다. 

MergeInternal(array, A, B, buffer)        // block swap the values in A with those in 'buffer' BlockSwap(array, A.start, buffer.start,  A )               A_count = 0, B_count = 0, insert = 0        while (A_count <  A  and B_count <  B )            if (array[buffer.start + A_count] ≤ array[B.start + B_count])스왑(array[A.start + insert], 어레이[buffer.start + A_count])A_count++ 다른 스왑(array[A.start + insert], 어레이[B.start + B_count])B_count++ insert+ // block swap의 나머지 부분과 어레이 BlockSwap(array, buffer.start + A_count, A.start + insert, A - A_count)의 나머지 부분을 교환한다.

두 번째 버퍼가 존재하지 않는 경우 황과 린 알고리즘의 회전 기반 버전,[7][8] 더진스키와 다이덱 알고리즘,[9] 또는 반복적인 바이너리 검색 및 회전과 같은 엄격히 인플레이스 병합 작업을 수행해야 한다. 

MergeInPlace(어레이, A, B) 중 // (A > 0 및 B > 0) // A의 첫 번째 항목을 중간 = BinaryFirst(어레이, 어레이[A.start], B) // A를 제자리에 양 = 중간 - A.end Rotate(어레이, 양, [A.start, 중간)로 삽입해야 하는 B에서 첫 번째 위치를 찾음// 새 A 및 B 범위 B = [중간, B.end] A = [A.start + 양, 중간) A.start = BinaryLast(어레이, 어레이[A.start], A)

최소 A 블록을 떨어뜨리고 이전 A 블록을 그 블록에 따르는 B 값과 병합한 후 어레이를 통해 롤링되고 있는 블록 내에서 새로운 최소 A 블록을 찾아야 한다.이 작업은 A 블록을 통해 선형 검색을 실행하고 태그 값을 비교하여 가장 작은 블록을 찾는 방식으로 처리된다. 

minA = blockA.start for (findA = minA + block_size; findA < blockA.end - 1, findA + 1; findA + = block_size) 만약 (array[findA + 1] < 배열[minA + 1]) minA = findA

이 나머지 A 블록은 계속해서 어레이를 롤링하여 해당 블록이 속한 위치에 드롭되고 삽입된다.이 과정은 A 블록이 모두 떨어져 이전 B 블록으로 회전될 때까지 반복된다.

마지막으로 남아 있는 A 블록을 뒤로 떨어뜨려 B 블록이 속한 곳에 삽입하면 그 블록을 따르는 나머지 B 값과 병합해야 한다.이렇게 하면 특정 쌍의 A와 B 하위선에 대한 병합 프로세스가 완료된다.그러나 그 다음 현재 수준의 병합 정렬에 대해 나머지 A 및 B 하위선에 대해 프로세스를 반복해야 한다.

이 수준의 병합 정렬에 대해 A 및 B 하위 배열의 모든 세트에 대해 내부 버퍼를 재사용할 수 있으며, 어떤 방식으로든 다시 추출하거나 수정할 필요가 없다는 점에 유의하십시오.

재배포

A와 B 하위선이 모두 합쳐진 후에도 한두 개의 내부 버퍼는 여전히 남아 있다.첫 번째 내부 버퍼는 A 블록에 태그를 붙이는 데 사용되었고, 내용물은 여전히 이전과 같은 순서로 되어 있지만, 두 번째 내부 버퍼는 병합의 스왑 공간으로 사용되었을 때 내용물이 재배열되었을 수 있다.이것은 두 번째 버퍼의 내용이 삽입 정렬과 같은 다른 알고리즘을 사용하여 정렬되어야 한다는 것을 의미한다.그런 다음 두 개의 버퍼를 만드는 데 사용된 반대 프로세스를 사용하여 다시 어레이로 배포해야 한다.

상향식 병합 정렬의 모든 레벨에 대해 이 단계를 반복하면 블록 정렬이 완료된다.

변형

블록 정렬은 A와 B 하위선을 균일한 크기의 블록으로 쪼개서 A 블록을 B로 굴려 떨어뜨리고(A 블록의 순서를 추적하기 위해 첫 번째 버퍼를 사용), 두 번째 버퍼를 스왑 공간으로 사용하여 로컬 병합하며 두 번째 버퍼를 정렬하고 두 번째 버퍼를 모두 재분배하는 방식으로 작동한다.단계는 변경되지 않지만, 이러한 하위 시스템은 실제 구현에 따라 달라질 수 있다.

블록 정렬의 한 변종은 A가 들어갈 때마다 A 하위 어레이 또는 A 블록을 B와 병합하는 데 이 외부 버퍼를 사용함으로써, 제공된 추가 메모리를 얼마든지 사용할 수 있게 한다.이런 상황에서 그것은 병합 분류와 동일할 것이다.

버퍼 크기에 대한 좋은 선택은 다음과 같다.

크기 메모들
(카운트 + 1)/2 A 하위선이 모두 들어맞기 때문에 고속 병합으로 변한다.
√(카운트 + 1)/2 + 1 이것은 가장 큰 수준의 병합에서 A 블록의 크기가 되므로 블록 정렬은 내부 또는 내부 병합에서 건너뛸 수 있음
512 병합 정렬의 더 작은 수준에서 수많은 병합 작업을 처리할 수 있을 만큼 큰 고정 크기 버퍼
0 시스템이 추가 메모리를 할당할 수 없는 경우, 어떤 메모리도 제대로 작동하지 않음

내부 버퍼 중 하나의 내용을 사용하여 A 블록에 태그를 지정하는 대신 간접 이동-이미징 버퍼를 사용할 수 있다.[1][10]이것은 s1 t s2로 정의된 내부 버퍼로, 여기서 s1과 s2는 각각 A와 B 블록의 수만큼 크며 t는 s1의 마지막 값과 동일한 s1 바로 뒤의 값을 포함한다(s1에 s2의 값이 나타나지 않음을 보장함).√A 고유값을 포함하는 두 번째 내부 버퍼가 여전히 사용된다.그런 다음 s1과 s2의 첫 번째 √A 값을 서로 교환하여 어떤 블록이 A 블록이고 어떤 블록이 B 블록인지에 대한 정보를 버퍼에 인코딩한다.인덱스 i에서 A 블록을 인덱스 j에서 B 블록과 교환할 때(첫 번째 균일한 크기 A 블록은 인덱스 0에 처음), s1[i]과 s1[j]은 각각 s2[i]와 s2[j]로 교환한다.이것은 A 블록에서 B 블록까지의 움직임을 모방한다.두 번째 버퍼의 고유 값은 A 블록이 B 블록을 통해 롤링될 때 원래 순서를 결정하는 데 사용된다.A 블록이 모두 삭제되면, 이동-이미징 버퍼를 사용하여 어레이의 주어진 블록이 A 블록인지 B 블록인지, 각 A 블록이 B 블록으로 회전하고, 두 번째 내부 버퍼가 로컬 병합의 스왑 공간으로 사용된다.

각 A 블록의 두 번째 값은 반드시 태그가 붙을 필요는 없다. 즉, 첫 번째, 마지막 또는 다른 요소를 대신 사용할 수 있다.그러나 첫 번째 값이 태그된 경우 최소 A 블록을 놓을 위치를 결정할 때 첫 번째 내부 버퍼(스왑된 위치)에서 값을 읽어야 한다.

버퍼의 내용이 고유하게 보장되기 때문에 퀵소트처럼 불안정한 정렬을 포함하여 제2의 내부 버퍼의 내용을 정렬하는 데 많은 정렬 알고리즘을 사용할 수 있다.그러나 삽입 분류는 상황적 성과와 반복의 결여 때문에 여전히 권장된다.

분석

블록 정렬(Block sort)은 잘 정의되고 테스트 가능한 알고리즘 등급으로, 작업 구현을 병합 및 정렬로 사용할 수 있다.[11][12][13]이를 통해 그 특성을 측정하고 고려할 수 있다.

복잡성

블록 정렬은 배열의 16~31개 항목 그룹에 삽입 정렬을 수행하는 것으로 시작한다.삽입 정렬은 O(n2) 연산이기 때문에 O(162 × n/16)부터 O(312 × n/31)까지의 어느 곳에도 이르는데, 상수 인자가 생략되면 O(n)가 된다.또한 각 수준의 합병이 완료된 후 두 번째 내부 버퍼에도 삽입 정렬을 적용해야 한다.그러나 이 버퍼의 크기는 √A로 한정되었기 때문에 O(√n2) 연산도 O(n)로 끝난다.

다음에는 병합 정렬의 각 수준에 대해 두 개의 내부 버퍼를 추출해야 한다.그것은 A와 B 하위선의 항목들을 반복하고 값이 변할 때마다 카운터를 증가시키며, 충분한 값을 찾으면 그것들을 A의 시작이나 B의 끝으로 회전시킨다.최악의 경우 이는 thisA 비연속 고유값을 찾기 전에 전체 어레이를 검색하게 되며, √A 값에 대한 O(n) 비교와 √A 회전이 필요하다.이것은 O(n + +n × √n) 또는 O(n)로 해결된다.

내부 버퍼를 생성하기 위한 orA 고유값을 포함하고 있는 A 또는 B 하위선이 없을 경우, 반복적으로 이진 검색하여 A를 B로 회전시키는 차선 내 병합 작업이 일반적으로 수행된다.그러나 하위선 내에서 고유한 값이 없는 것으로 알려져 이 단계 동안 수행될 이진수 검색 및 회전 수에 엄격한 제한이 있으며, 다시 √A 횟수 또는 O(n)까지 회전한 √A 항목이다.각 블록의 크기 또한 √A 고유값을 발견한 경우 2√A가 아닌 경우에 더 작게 조정되어 A 또는 B 블록에 포함된 고유값의 수를 더욱 제한한다.

A 블록 태그 지정은 각 A 서브 어레이에 대해 forA회 수행된 다음, A 블록을 롤링하여 B 블록에 최대 aA회까지 삽입한다.로컬 병합은 표준 병합과 동일한 O(n) 복잡성을 유지하지만 값을 복사하기보다는 교환해야 하기 때문에 할당량이 더 많다.새로운 최소 A 블록을 찾기 위한 선형 검색은 √A 블록에 걸쳐 반복된다.그리고 버퍼 재분배 과정은 버퍼 추출과 동일하지만 역방향이기 때문에 O(n) 복잡성이 동일하다.

가장 높은 복잡성을 제외한 모든 복잡성을 생략하고 외부 병합 루프에 로그 n 수준이 있다는 점을 고려한 후, 이는 최악의 경우와 평균적인 경우 최종 점증상 복잡성을 야기한다.최상의 경우, 데이터가 이미 순서대로 정렬되어 있는 경우, 병합 단계는 첫 번째 수준에 대해 n/16 비교를 수행한 다음, n/32, n/64, n/128 등을 수행한다.이것은 O(n)로 분해되는 잘 알려진 수학 시리즈다.

기억력

블록 정렬은 반복되지 않고 동적 할당을 사용할 필요가 없으므로, 이는 일정한 스택 및 힙 공간을 초래한다.Transdicotomous 모델에서 O(1) 보조 메모리를 사용하며, 이는 A와 B의 범위를 추적하는 데 필요한 O(log n) 비트가 각각 32비트 또는 64비트 컴퓨팅 시스템에서 32 또는 64보다 클 수 없다는 것을 수용하며, 따라서 타당하게 할당될 수 있는 어레이의 경우 O(1) 공간으로 단순화한다.

안정성

비록 배열에 있는 아이템들이 블록 정렬 중에 순서에 맞지 않게 이동되지만, 각각의 동작은 완전히 되돌릴 수 있고, 그것의 완료에 의해 동급의 아이템들의 원래 순서를 복원하게 될 것이다.

안정성은 정렬하기 전에 배열에서 각 값의 첫 번째 인스턴스가 여전히 정렬 후 해당 값의 첫 번째 인스턴스가 되어야 한다.블록 정렬은 이러한 첫 번째 인스턴스를 어레이의 시작 부분으로 이동하여 두 개의 내부 버퍼를 만들지만, 블록 정렬의 현재 수준에 대해 모든 병합이 완료되면 해당 값이 어레이 내의 첫 번째 정렬 위치로 다시 분산된다.이것은 안정을 유지한다.

A 블록을 B 블록으로 굴리기 전에 각 A 블록은 두 번째 값을 첫 번째 버퍼의 값으로 교환한다.이때 A 블록은 B 블록을 굴리기 위해 순서대로 이동한다.그러나 이전 B 블록에 가장 작은 A 블록을 삽입해야 하는 위치를 찾으면 그 가장 작은 A 블록이 A 블록의 시작 부분으로 다시 이동되고 두 번째 값이 복원된다.A 블록이 모두 삽입될 때쯤이면 A 블록이 다시 순서대로 배열되고 첫 번째 버퍼에는 원래 순서대로 원래 값이 들어 있게 된다.

A 블록을 일부 B 값과 병합할 때 두 번째 버퍼를 스왑 공간으로 사용하면 해당 버퍼의 내용이 다시 정렬된다.그러나 알고리즘은 이미 버퍼에 고유한 값만 포함하도록 보장했기 때문에, 버퍼의 내용을 정렬하면 원래의 안정된 질서를 회복하기에 충분하다.

적응성

블록 정렬은 두 가지 수준에서 적응형 정렬이다. 첫째, 이미 순서가 정해진 A와 B 하위 정렬을 생략한다.다음으로 A와 B를 병합하여 균일한 크기의 블록으로 분할해야 할 때, A 블록은 필요한 범위 내에서 B를 통해서만 굴려지며, 각 블록은 그 직후에 B 값과 병합될 뿐이다.원래 데이터가 많이 순서가 잡힐수록 A로 병합해야 하는 B 값이 줄어들게 된다.

이점

블록 정렬은 추가 메모리가 필요 없는 안정적인 정렬로, O(n) 버퍼를 할당할 수 있는 여유 메모리가 부족한 경우에 유용하다.블록 정렬의 외부 버퍼 변형을 사용할 경우 필요에 따라 O(n) 메모리를 사용하는 것에서 점진적으로 작은 버퍼로 확장할 수 있으며, 이러한 제약 조건 내에서 여전히 효율적으로 작동할 것이다.

단점들

블록 정렬은 Timsort와 같은 일부 다른 알고리즘처럼 미세한 수준의 정렬된 데이터 범위를 이용하지 않는다.[14]A와 B 하위 선과 A와 B 블록의 사전 정의된 두 수준에서 정렬된 범위만 검사한다.또한 병합 분류에 비해 구현과 병렬화가 더 어렵다.

참조

  1. ^ a b Kutzner, Arne; Kim, Pok-Son (2008). Ratio Based Stable In-Place Merging (PDF). Lecture Notes in Computer Science. Vol. 4978. Springer Berlin Heidelberg. pp. 246–257. Retrieved 2016-09-07.
  2. ^ Mannila, Heikki; Ukkonen, Esko (14 May 1984). "A Simple Linear Time Algorithm for In-Situ Merging". Information Processing Letters. 18 (4): 203–208. doi:10.1016/0020-0190(84)90112-1.
  3. ^ Kronrod, M. Alexander (February 1969). "Оптимальный алгоритм упорядочения без рабочего поля" [An Optimal Ordering Algorithm without a Field of Operation]. Proceedings of the USSR Academy of Sciences (in Russian). 186 (6): 1256–1258.
  4. ^ Bentley, Jon (2006). Programming Pearls (2nd ed.).
  5. ^ Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.
  6. ^ Pardo, Luis Trabb (1977). Stable Sorting and Merging with Optimal Space and Time Bounds. SIAM Journal on Computing. Vol. 6. pp. 351–372.
  7. ^ a b Geffert, Viliam; Katajainen, Jykri; Pasanen, Tomi (April 2000). "Asymptotically efficient in-place merging". Theoretical Computer Science. 237 (1–2): 159–181. CiteSeerX 10.1.1.22.5750. doi:10.1016/S0304-3975(98)00162-5.
  8. ^ Hwang, F. K.; Lin, S. (1972). A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets. SIAM Journal on Computing. Vol. 1. pp. 31–39. doi:10.1137/0201004. ISSN 0097-5397.
  9. ^ Dudzinski, Krzysztof; Dydek, Andrzej (1981). On a Stable Storage Merging Algorithm. Information Processing Letters. Vol. 12. pp. 5–8.
  10. ^ Symvonis, Antonios (1995). "Optimal Stable Merging". The Computer Journal. 38 (8): 681–690. CiteSeerX 10.1.1.55.6058. doi:10.1093/comjnl/38.8.681.
  11. ^ Arne Kutzner. "In-place Merging Algorithm Benchmarking Tool". Archived from the original on 2014-04-15. Retrieved 2014-03-23.
  12. ^ Arne Kutzner. "In-place Merging Algorithm Benchmarking Tool". Archived from the original on 2016-12-20. Retrieved 2016-12-11.
  13. ^ "Public domain implementations of block sort for C, C++, and Java". Retrieved 2014-03-23.
  14. ^ Tim Peters. "Re: WikiSort". Retrieved 2020-09-13.