0

かなり長い間デバッグできないという問題がありました。「Algorithm's in C++」本で Robert Sedgewick のアルゴリズムに従って、配列コピーの追加手順なしで MergeSort アルゴリズムを実装しようとしています。
アルゴリズムの簡単な説明:

再帰プログラムは、b を並べ替え、結果を a に残すように設定されています。したがって、再帰呼び出しは結果を b に残すように記述され、基本的なマージ プログラムを使用してこれらのファイルを b から a にマージします。このようにして、マージ中にすべてのデータ移動が行われます。

問題は、論理エラーが見つからないことですが、並べ替えが適切に行われていません。データがどこかで上書きされ、これを引き起こしている論理エラーを特定できません。プログラムが終了するとデータはソートされますが、それはもはや同じデータではありません。
たとえば、入力配列:は配列:{ A, Z, W, B, G, C }を生成します{ A, G, W, W, Z, Z }。

どこかで論理エラーに違いないことは明らかですが、かなり長い間これをデバッグしようとしてきましたが、実際には何も見つからないため、何が欠けているのかを新鮮な目で見ることができると思います違う。

私が実行している完全なコード:

//Here is my complete code that I run and that behaves as specified above.

#include <iostream>
#include <stdlib.h>

using namespace std;

// function to print the array
void print(char * a[],int l, int r)
{ for(int i=l;i<=r;i++) cout << (i+1) << ": " << a[i] << endl; }

static const int M = 1;

void insertion(char** a, int l, int r)
{ int i,j;
  char * temp;
  for(i=1;i<r+1;i++)
  { temp = a[i];
    j = i;
    while((j>0) && strcmp(a[j-1],temp)>0)
    { a[j] = a[j-1];
      j = j - 1; }
     a[j] = temp; } }

//merging a and b into c
void merge(char ** c,char ** a, int N, char ** b, int M)
{ for (int i=0, j=0, k=0; k<(N+M); k++)
  { if(i == N) {c[k] = b[j++]; continue; }
if(j == M) {c[k] = a[i++]; continue; }
c[k] = strcmp(a[i], b[j])<0 ? a[i++] : b[j++]; } }

 void mergesortAux(char ** a, char ** b, int l, int r)
 { if(r-l <= M) { insertion(a, l, r); return; }
   int m = (l+r)/2;
   mergesortAux(b, a, l, m);        //merge sort left
   mergesortAux(b, a, m+1, r);      //merge sort right
   merge(a+l,b+l,m-l+1,b+m+1,r-m);  }       //merge

void mergesort(char ** a,int l, int r, int size)
{ static char ** aux = (char**)malloc(size*sizeof(char*));
  for(int i = l; i<size; i++) aux[i] = a[i];
  mergesortAux(a,aux,l,r); }
 //free(aux); } I removed this piece of code as suggested, I realize it's unnecessary 

int main(int argc, char * argv[]) 
{ int size = 6;
  char **data = (char**)malloc(size*sizeof(char*));
  data[0] = "A";
  data[1] = "Z";
  data[2] = "W";
  data[3] = "B";
  data[4] = "G";
  data[5] = "C";

  print(data,0,size-1);
  printf("---------------------------\n");

  mergesort(data,0,size-1,size);

  printf("---------------------------\n");
  print(data,0,size-1);
  return 0;
}

出力：

1: A
2: Z
3: W
4: B
5: G
6: C
---------------------------
---------------------------
1: A
2: G
3: W
4: W
5: Z
6: Z
4

1 に答える 1