Алгоритм сортировки слияния?

Question

Я не могу понять, что не так с моей функцией MergeSort. Это мой код:

void Merge(int* A, int p, int q, int r) 
{ 
    int B[100], i = 0, j = 0, k = 0; 

    i = p; 
    k = p; 
    j = q + 1; 

    while (i <= q && j <= r) 
    { 
     if (A[i] <= A[j]) 
     { 
      B[k] = A[i]; 
      k++; 
      i++; 
     } 

     else 
     { 
      B[k] = A[j]; 
      k++; 
      j++; 
     } 
    } 

    while (i <= q) 
    { 
     B[k] = A[i]; 
     k++; 
     i++; 
    } 

    while (j <= r) 
    { 
     B[k] = A[j]; 
     k++; 
     j++; 
    } 

    for (i = p; i < r; i++) 
    { 
     A[i] = B[i]; 
    } 
} 


void MergeSort(int A[], int p, int r) 
{ 
    int q; 

    if (p < r) 
    { 
     q = (p + r)/2; 
     MergeSort(A, p, q); 
     MergeSort(A, q + 1, r); 
     Merge(A, p, q, r); 
    } 
} 


int main(void) 
{ 
    int N[10]; 

    N[0] = 4; 
    N[1] = 5; 
    N[2] = 8; 
    N[3] = 12; 
    N[4] = 7; 
    N[5] = 3; 
    N[6] = 23; 
    N[7] = 1; 
    N[8] = 90; 
    N[9] = 26; 

    MergeSort(N, 0, 9); 

    for (int i = 0; i < 10; i++) 
    { 
     cout << N[i] << endl; 
    } 
} 

Выход программы: 1, 3, 1, 4, 5, 7, 7, 7, 26, 26, что, очевидно, не так. Однако я просто не вижу, что не так в коде, для меня все выглядит хорошо. Я googled некоторые C++ коды MargeSort и попытаться отладить его, но я не могу найти ошибку. Кто-нибудь это видит?

Answer 1

// у вас есть только один ERR, в прошлом для вас пропустили =:

// ERR: для (я = р; я < г; я ++)

// правильно: для (I = р, я < = г; я ++)

#include <iostream> 
using namespace std; 
void Merge(int* A, int p, int q, int r) 
{ 
    int B[100], i = 0, j = 0, k = 0; 
    i = p; 
    k = p; 
    j = q + 1; 
    while (i <= q && j <= r) 
    { 
     if (A[i] <= A[j]) 
     { 
      B[k] = A[i]; 
      k++; 
      i++; 
     } 
     else 
     { 
      B[k] = A[j]; 
      k++; 
      j++; 
     } 
    } 

    while (i <= q) 
    { 
     B[k] = A[i]; 
     k++; 
     i++; 
    } 

    while (j <= r) 
    { 
     B[k] = A[j]; 
     k++; 
     j++; 
    } 

    for (i = p; i <= r; i++) 
    { 
     A[i] = B[i]; 
    } 
} 

void MergeSort(int A[], int p, int r) 
{ 
    int q; 

    if (p < r) 
    { 
     q = (p + r)/2; 
     MergeSort(A, p, q); 
     MergeSort(A, q + 1, r); 
     Merge(A, p, q, r); 
    } 
} 


int main(void) 
{ 
    int A[10]={9,8,7,6,5,4,3,2,1,0}; 
    MergeSort(A,0,9); 
    for (int i = 0; i<10; i++) 
    { 
     cout<<A[i]<<","; 
    } 
} 

// это чистят версия кода:

#include <iostream> 
using namespace std; 
void Merge(int* A, int p, int q, int r) 
{ 
    int* B=new int[r-p+1]; 
    int i = p; 
    int j = q + 1; 
    int k = 0; 
    while (i <= q && j <= r) B[k++] = (A[i] <= A[j])? A[i++] : A[j++]; 
    while (i <= q) B[k++] = A[i++]; 
    while (j <= r) B[k++] = A[j++]; 
    for (i = p; i <= r; i++) A[i] = B[i-p]; 
    delete B; 
} 
void MergeSort(int* A, int p, int r) 
{ 
    if (p >= r) return; 
    int q = (p + r)/2; 
    MergeSort(A, p, q); 
    MergeSort(A, q + 1, r); 
    Merge(A, p, q, r); 
} 
int main(void) 
{ 
    int A[15]={10,11,12,13,14,0,8,7,6,5,4,3,2,1,9}; 
    MergeSort(A,0,14); 
    for (int i = 0; i<15; i++) cout<<A[i]<<","; 
} 

// это nother ответ:

#include <iostream> 
#include <climits> 
using namespace std; 
static void Merge(int* A, int p, int q, int r) 
{ 
    int n1 = q - p + 1;// A[p..q] 
    int n2 = r - q;// A[q+1..r] 
    int* L = new int[n1 + 1]; 
    int* R = new int[n2 + 1]; 
    int i, j; 
    for (i = 0; i < n1; i++) 
     L[i] = A[p + i]; 
    for (i = 0; i < n2; i++) 
     R[i] = A[q + i+1]; 
    L[n1] = INT_MAX; 
    R[n2] = INT_MAX; 
    i = 0; 
    j = 0; 
    for (int k = p; k <= r; k++) 
     A[k] = L[i] <= R[j] ? L[i++] : R[j++]; 
    delete L; 
    delete R; 
} 
static void Ascending(int* A, int p, int r) 
{ 
    if (p >= r) return; 
    int q = (p + r)/2; 
    Ascending(A, p, q); 
    Ascending(A, q + 1, r); 
    Merge(A, p, q, r); 
} 
int main() 
{ 
    int A[10]={9,8,7,6,5,4,3,2,1,0}; 
    Ascending(A,0,9); 
    for (int i = 0; i<10; i++) 
    { 
     cout<<A[i]<<","; 
    } 
}