병합 정렬 최적화 이해 : 복사본 피하기

Question

아래에 병합 정렬 프로그램이 있습니다. 주요 문제는 두 개의 정렬 된 목록을 병합하려면 선형 추가 메모리가 필요하며 추가 작업이 임시 배열에 복사하고 다시 사용하는 것입니다. 알고리즘 전반에 걸쳐 정렬 속도를 상당히 늦추는 효과가 있습니다. 이 복제는 재귀 수준에서 "a"및 "tmp_array"의 역할을 적절하게 전환하여 피할 수 있습니다.

제 질문은 저자가 "반복적 인 수준의 재귀 수준에서 a 및 tmp_array의 역할을 적절하게 전환하여 복사를 피할 수있다"는 의미이며 다음 코드에서 어떻게 가능합니까? 우리가 이것을 어떻게 달성 할 수 있는지 예를 보여달라고 요청합니까?

void mergesort(input_type a[], unsigned int n) { 

    input_type *tmp_array; 
    tmp_array = (input_type *) malloc((n+1) * sizeof (input_type)); 
    m_sort(a, tmp_array, 1, n); 
    free(tmp_array); 
} 

void m_sort(input_type a[], input_type tmp_array[ ], int left, int right) { 

    int center; 
    if(left < right) { 

    center = (left + right)/2; 
    m_sort(a, tmp_array, left, center); 
    m_sort(a, tmp_array, center+1, right); 
    merge(a, tmp_array, left, center+1, right); 
    } 
} 

void merge(input_type a[ ], input_type tmp_array[ ], int l_pos, int r_pos, int right_end) { 

    int i, left_end, num_elements, tmp_pos; 
    left_end = r_pos - 1; 
    tmp_pos = l_pos; 
    num_elements = right_end - l_pos + 1; 

    /* main loop */ 

    while((1_pos <= left_end) && (r_pos <= right_end)) 

     if(a[1_pos] <= a[r_pos]) 
      tmp_array[tmp_pos++] = a[l_pos++]; 
     else 
      tmp_array[tmp_pos++] = a[r_pos++]; 

    while(l_pos <= left_end) /* copy rest of first half */ 
     tmp_array[tmp_pos++] = a[l_pos++]; 

    while(r_pos <= right_end) /* copy rest of second half */ 
     tmp_array[tmp_pos++] = a[r_pos++]; 

    /* copy tmp_array back */ 
    for(i=1; i <= num_elements; i++, right_end--) 
     a[right_end] = tmp_array[right_end]; 

} 

Answer 1

이런 식으로 병합 정렬을 생각해보십시오.

0 길이 1

1 명령 시퀀스의 집합으로 입력 배열 A0 고려하십시오 새로운 임시 배열 A1을 구성, A0에서 시퀀스의 각각의 연속 쌍을 병합.

2 : 새로운 임시 배열 A2를 구성하여 A1에서 연속 된 각 쌍을 병합합니다.

...

완료되면 단일 시퀀스의 마지막 반복의 결과.

0 : 이제

, 당신은 분명히 이렇게 단 하나의 임시 배열 멀리 얻을 수 길이의 명령 시퀀스의 컬렉션으로 입력 배열 A0을 고려 1.

1 : A0의 각 연속적인 쌍을 병합하고 새로운 임시 배열 A1을 구성합니다.

2 : A0 을 덮어 쓰고 A1에서 연속 된 각 쌍을 병합합니다.

3 : 결과를 A1 을 덮어 쓰고 A0의 각 연속적인 쌍을 병합합니다.

...

마지막 반복이 단일 시퀀스가 ​​될 때 마침.

물론 이보다 더 똑똑 할 수도 있습니다. 캐시에 더 좋기를 원한다면 상향식이 아닌 하향식으로 정렬 할 수 있습니다. 이 경우, 교과서가 다른 수준의 재귀 수준에서 배열의 역할을 추적 할 때 교과서가 의미하는 바가 무엇인지 분명하게 알 수 있습니다.

희망이 도움이됩니다.

Answer 2

병합 기능의 마지막 부분을 살펴보십시오. 이 데이터를 복사하는 대신 함수가 반환 될 때 a 대신에 tmp_array에 정렬 된 부분이 있다는 지식을 사용하고 a을 임시로 사용할 수 있다면 어떨까요?

자세한 내용은 독자를위한 연습 과제로 남겨 둡니다.

Answer 3

이 코드를 보지 않고는 원본 크기와 동일한 크기의 인접한 메모리 블록을 선언하여 병합 정렬을 수행한다고 가정합니다.

그래서 일반적으로 다음과 같이 일종의 병합 : 반

• 분할 배열
• 종류의 재귀 적

I

병합 반 배열 다시에 머지 소트를 호출하여 반 배열 재귀 적이라고 가정하고 크기가 2 인 하위 배열을 정렬하기 전에 복사가 수행되지 않습니다. 이제 어떻게됩니까?

_ means it is memory we have available, but we don't care about the data in it 

original: 
    8 5 2 3  1 7 4 6 
    _ _ _ _  _ _ _ _ 

시작 재귀 호출 :

recursive call 1: 
    (8 5 2 3) (1 7 4 6) 
    _ _ _ _  _ _ _ _ 

recursive call 2: 
((8 5) (2 3)) ((1 7) (4 6)) 
    _ _ _ _  _ _ _ _ 

recursive call 3: 
(((8) (5))((2) (3)))(((1) (7))((4) (6))) 
    _ _ _ _  _ _ _ _ 

재귀 합병으로 해결 전화, PLUS COPYING (느린 방법) :

저자가 함께 해결 재귀 호출을 제안 무엇

merge for call 3, using temp space: 
(((8) (5))((2) (3)))(((1) (7))((4) (6))) --\ perform merge 
((5 8)(2 3))((1 7)(4 6)) <--/ operation 

UNNECESSARY: copy back: 
((5 8)(2 3))((1 7)(4 6)) <--\ copy and 
    _ _ _ _  _ _ _ _  --/ ignore old 

merge for call 2, using temp space: 
((5 8)(2 3))((1 7)(4 6)) --\ perform merge 
( 2 3 5 8 )( 1 4 6 7 ) <--/ operation 

UNNECESSARY: copy back: 
( 2 3 5 8 )( 1 4 6 7 ) <--\ copy and 
    _ _ _ _  _ _ _ _  --/ ignore old 

merge for call 1, using temp space: 
( 2 3 5 8 )( 1 4 6 7 ) --\ perform merge 
    1 2 3 4  5 6 7 8  <--/ operation 

UNNECESSARY: copy back: 
    1 2 3 4  5 6 7 8  <--\ copy and 
    _ _ _ _  _ _ _ _  --/ ignore old 

병합, 복사하지 않고 (더 빠른 방법) :

merge for call 3, using temp space: 
(((8) (5))((2) (3)))(((1) (7))((4) (6))) --\ perform merge 
((5 8)(2 3))((1 7)(4 6)) <--/ operation 

merge for call 2, using old array as temp space: 
( 2 3 5 8 )( 1 4 6 7 ) <--\ perform merge 
((5 8)(2 3))((1 7)(4 6)) --/ operation (backwards) 

merge for call 1, using temp space: 
( 2 3 5 8 )( 1 4 6 7 ) --\ perform merge 
    1 2 3 4  5 6 7 8  <--/ operation 

위와 같이 잠금 단계에서 병합 정렬 트리의 각 "수준"을 수행하는 동안 복사본을 만들 필요가 없습니다.

위에서 설명한 바와 같이 약간의 패리티가있을 수 있습니다. 즉, 귀하의 결과는 귀하의 temp_array에있을 수 있습니다. 당신이 처리하기위한 세 가지 옵션 중 하나를

는 단일 배열 복사 작업을 수행합니다 (응용 프로그램이 괜찮 경우) 기존 메모리를 답으로 temp_array를 반환

• 및 해제, temp_array를 복사
• 두 배의 메모리를 소비하고 temp_array1에서 temp_array2까지의 단일주기를 수행 한 다음 original_array으로 돌아온 다음 temp_array2을 릴리스하십시오. 패리티 문제는 해결되어야합니다.

Answer 4

다음은 추가 사본이없는 구현입니다.

public static void sort(ArrayList<Integer> input) { 
    mergeSort(input, 0, input.size() - 1); 
} 

/** 
* Sorts input and returns inversions number 
* using classical divide and conquer approach 
* 
* @param input Input array 
* @param start Start index 
* @param end End index 
* @return int 
*/ 
private static long mergeSort(ArrayList<Integer> input, int start, int end) { 
    if (end - start < 1) { 
     return 0; 
    } 

    long inversionsNumber = 0; 

    // 1. divide input into subtasks 
    int pivot = start + (int) Math.ceil((end - start)/2); 
    if (end - start > 1) { 
     inversionsNumber += mergeSort(input, start, pivot); 
     inversionsNumber += mergeSort(input, pivot + 1, end); 
    } 

    // 2. Merge the results 
    int offset = 0; 
    int leftIndex = start; 
    int rightIndex = pivot + 1; 
    while (leftIndex <= pivot && rightIndex <= end) { 
     if (input.get(leftIndex + offset) <= input.get(rightIndex)) { 
      if (leftIndex < pivot) { 
       leftIndex++; 
      } else { 
       rightIndex++; 
      } 
      continue; 
     } 

     moveElement(input, rightIndex, leftIndex + offset); 
     inversionsNumber += rightIndex - leftIndex - offset; 
     rightIndex++; 
     offset++; 
    } 

    return inversionsNumber; 
} 

private static void moveElement(ArrayList<Integer> input, int from, int to) { 
    assert 0 <= to; 
    assert to < from; 
    assert from < input.size(); 

    int temp = input.get(from); 
    for (int i = from; i > to; i--) { 
     input.set(i, input.get(i - 1)); 
    } 
    input.set(to, temp); 
}