병합 정렬 알고리즘이 제대로 병합되지 않습니다.

Question

병합 정렬이 수행해야하는 작업을 알고 있으며 지금은 다소 시각화 할 수 있습니다. 한 요소의 배열이 이미 정렬되어 있기 때문에 하나의 요소 만 배열에 남아있을 때까지 반복적으로 분할하면 각 재귀에 필요한 작업량이 줄어들고 이미 정렬 된 배열을 다른 배열에 추가하는 것보다 정상 반복으로 정렬하십시오.

저는 현재 두 가지 주요 문제가 있습니다. 하나, 분할 (단순한 것이지만 고정되지 않으면 모든 것을 버릴 것입니다.), 저 -> 중반 (+/- 1) 및 중간 -> 고갈로 갈라 놓으면 문제가 생깁니다. 기본 사례가 제대로 테스트되지 않고 조기에 반환되어 정렬되지 않은 배열이 발생합니다. 예를 들어, 다른 포럼의 답장을 인용하면 "5 명이 중간, 9 명이 좋고 0 명이 적다면 0에서 5로 오른쪽으로 나눠야하고 6에서 9로 왼쪽으로 나눠야합니다. 또는 오른쪽으로 0에서 4, 왼쪽에서 5로 9입니다. 문제는 6에서 9로 다시 나누면 반올림으로 인해 중간이 7이므로 오른쪽에서 6에서 7까지만 사용한다는 것입니다. 7 - 6이 1이고 2보다 작 으면 2보다 작을 경우 실패하고 2는 잠재적으로 분류되지 않은 요소가됩니다. "

이제는 두 가지 중 어느 하나라도 중간에 +/-를 추가하면 잘 작동하지 않는 홀수가 낮은 숫자가됩니다. 이 문제를 어떻게 해결할 수 있습니까?

둘째, 병합과 관련하여 B'sand C의 배열 범위가 적절한 지 여부를 올바르게 (그리고 효율적으로) 확인하는 방법은 무엇입니까? PosB와 PosC가 경계에 있는지 여부를 확인하기 위해 또 다른 조건문이 필요합니까? 그렇지 않은 경우 어떻게 다른 배열의 왼쪽에있는 배열을 최종 배열에 적절하게 (그리고 깔끔하게) 추가 할 수 있습니까?

미리 감사드립니다. 이것은 시각적 인 기본에 있어야하지만, 지금은 의사 코드가 올바른 구문을 강조하기보다는 이러한 문제에 접근하는 가장 좋은 방법 인 것으로 보입니다.

당신이 당신의 결과 (6,7,8)의 3 개 요소가 6-8에서 위치를 액세스 할 때 :

A[] = { 28, 39, 48, 27, 9, 88, 11, 4, 7} ' Global variable, disregard bad programming practices 

Function Split(int low, int hi){ ' Adding brackets because not only am I used to java, it should help readability 
    if (hi - low) < 2 then 
     return array of elements from [low, hi] 
    end if 

    mid = (hi + low)/2 
    B[] = split(low, mid-1) ' Either I do mid-1 or mid+1, the results seem the same 
    C[] = split(mid, hi) ' Same problems as above 
    D[] = Merge(B[], C[]) 
    return D[] 
End Function 

Function Merge(B[], C[]) ' I use two arrays because I figured it'd be the easiest to work with. 
    int PosB = 0, PosC = 0, PosMax = (b.length + c.length) -1 ' PosB and PosC keep track of the positions in the cells of B and C respectively. 
                   'PosMax keeps track of the max cell that E[] (declared below) should have as well as the max number for the for loop 
    E[num] ' Declare and iniatialize an array that is supposed to hold the combined values of B and C, sorted. 
    for i = 0 to num 
     if PosC >= c.length or B[PosB] < C[PosC] ' Checks if C[] already has added everything it has to E[] and if so, proceeds to add the 
                ' supposedly already sorted array B[]'s elements to E[]. Emphasis on "supposedly". A problem here is it does not check for if PosB 
                ' is out of bounds, which is a huge problem with primitive arrays. Also checks if the current element in C is greater than the 
                ' current element in B, and if so, add the element in B and increment. 
      E[i] = B[PosB] 
      PosB += 1 ' Does not check whether or not PosB is at the end, gotta figure a way to check 
     Else 
      E[i] = C[PosC] 
      PosC += 1 
     End If 
    Next 
End Function 

Answer 1

문제는 배열의 경계가 의미하는 포괄적 있다는 것이다. 논리적 결과는 다음과 같습니다. 배열의 범위로 설명 된 요소 하나만 원할 경우 [6-6]; [6-7]은 여전히 ​​두 개의 요소 (6과 7)가 있음을 의미합니다. 예를 들어 다음 코드를 살펴 보겠습니다.

if (hi - low) < 2 then 
    return array of elements from [low, hi] 

6-7 범위에서이 기능을 사용하면 어떻게됩니까? 7-6 = 1 -> true -> 복귀. 그러나 6-7의 범위에서 여전히 두 가지 요소가 있습니다. 따라서이 문제를 해결하려면 (hi - low) == 0을 읽고 (hi - low) < 1으로 작성하거나 읽기가 쉬울 것입니다. 이 결과는 아마 낮은 값으로 반올림됩니다 정수를 (반환하면

mid = (hi + low)/2 

(3 : 그것은 내가 VBA를 잘 알고 아니에요처럼 생각, 그래서

다음 포인트는 VBA에 대한 자세한입니다 +4)/2 = 3). 그래서 나는 다음과 같은 쓰기 할 경우

B[] = split(low, mid) 
C[] = split(mid + 1, hi) 

그 이유는 mid가 아래쪽 테두리가 (반올림으로 인해) 이미 것입니다. 하위 분류 1은 음수 값을 초래할 수 있으므로 경계가 0에 가까울 때 몇 가지 문제가 발생할 수 있습니다.두 번째 부분에 대한

:

두 가지로 프로세스를 분할하는 것이 더 쉽습니다 :

E[num]' I don't know what num means but I suppose it's correct here 
int PosE = 0 
'adding elements to the new array while they can be compared to each other 
while(c.length > 0 and b.length > 0) 
    if(C[PosC] < B[PosB]) 
     E[PosE] = C[PosC] 
     PosC += 1 
    Else 
     E[PosE] = B[PosB] 
     PosB += 1 
    End If 
    PosE += 1 
Next 

'one of the array B or C (or both) is empty now. The remaining elements have to be added. The order doesn't matter any more. 

for i = PosC to c.length 'I don't know if this is possible in VBA but I think you know what I mean: adding all the remaining elements of C to E (if there are any) 
    E[PosE] = C[PosC] 
    PosC += 1 
    PosE += 1 
Next 

'doing the same with B; it could happen that one of those loops never run 
for i = PosB to b.length 
    E[PosE] = B[PosB] 
    PosB += 1 
    PosE += 1 
Next 

내가 VB에서 아무것도 작성 적이 있기 때문에이 작품 바랍니다.

질문이 있으시면 언제든지 문의하십시오.