修改合併排序用於存儲原始索引

Question

我試圖修改合併排序以存儲原始索引後修改它沒有正確排序..我無法找到我出錯的地方請幫我找到問題..

請在下面找到我的代碼。

void merge(int a[][2],int start,int middle ,int end) 
{ 
    int size1 = middle-start +1; 
    int size2 = end-middle; 
    int i,j; 
    int k =start; 
    int L[size1][2]; 
    int R[size2][2]; 
    //int *L = (int *)malloc(sizeof(int)*size1); 
    //int *R = (int *)malloc(sizeof(int)*size2); 

    // copy values from main array to temp arrays 
    for(i=0 ; i<size1; i++) 
    { 
     L[i][1] = a[i+start][1]; 
     L[i][0] = a[i+start][0]; 
    } 
    for(j=0 ; j<size2 ; j++) 
    { 
     R[j][1] = a[j+middle+1][1]; 
     R[j][0] = a[j+middle+1][0]; 
    } 

    i=0; 
    j=0; 
    while(i<size1 && j<size2) 
    { 
     if(L[i] < R[j]) 
     { 
      a[k][1] = L[i][1]; 
      a[k][0] = L[i][0]; 
      k++; 
      i++; 
     } 
     else{ 
      a[k][1] = R[j][1]; 
      a[k][0] = R[j][0]; 
      k++; 
      j++; 
     } 
    } 
    while(i<size1) 
    { 
     a[k][1] = L[i][1]; 
     a[k][0] = L[i][0]; 
     i++; 
     k++; 
    } 
    while(j<size2) 
    { 
     a[k][1] = R[j][1]; 
     a[k][0] = R[j][0]; 
     k++; 
     j++; 
    } 
} 

void mergeSort(int a[][2], int start , int end) 
{ 
    if(start < end) 
    { 
     int middle = start + (end - start) /2; 
     mergeSort(a,start, middle); 
     mergeSort(a,middle+1,end); 
     merge(a,start,middle,end); 
    } 
} 

int main() 
{ 
    int array[10][2] = {{0,55},{1,3},{2,4},{3,5},{4,6},{5,7},{6,8},{7,9},{8,10},{9,2}}; 
    int i; 
    int len = sizeof(array)/sizeof(array[0]) - 1; 
    for(i = 0 ;i <= 9; i++) 
     printf("%d",array[i][1]); 
    mergeSort(array,0,9); 
    printf ("\nArray after sorting:\n") ; 
    printf ("\nindex after sorting:\n") ; 
    for(i = 0 ;i <= 9; i++) 
     printf("%d",array[i][0]); 
    printf ("\nArray after sorting:\n") ; 
    for(i = 0 ;i <= 9; i++) 
     printf("%d",array[i][1]); 
} 

Answer 1

你的根本問題是在你的合併算法的初始while循環：

if(L[i] < R[j]) 

這是比較兩個int的內存地址[2]數組，而不是值在第二個插槽舉行同樣，這就是你應該做的。

if(L[i][1] < R[j][1]) 

這就是說，這可以做得相當簡單，但這是主要問題的關鍵。

---

指針數學版本

爲了補充我在這個答案下降了評論，以下是使用指針數學的段代碼的簡化版本分裂，而不是僅僅索引。仔細查看mergeSort()的遞歸調用以及參數。還要注意在merge算法使用單個臨時數組的索引：

void merge(int a[][2], int mid, int len) 
{ 
    int tmp[len][2]; 
    int i,j,k=0; 

    // copy values from main array to temp 
    memcpy(tmp, a, len*sizeof(*a)); 

    i=0; j=mid; 
    while(i<mid && j<len) 
    { 
     if (tmp[i][1] < tmp[j][1]) 
     { 
      // take from left side 
      a[k][1] = tmp[i][1]; 
      a[k][0] = tmp[i++][0]; 
     } 
     else 
     { // take from right side 
      a[k][1] = tmp[j][1]; 
      a[k][0] = tmp[j++][0]; 
     } 

     ++k; // always incremented 
    } 

    // one of these is skipped. the other will 
    // finish the merge algorithm 
    while(i<mid) 
    { 
     a[k][1] = tmp[i][1]; 
     a[k++][0] = tmp[i++][0]; 
    } 

    while(j<len) 
    { 
     a[k][1] = tmp[j][1]; 
     a[k++][0] = tmp[j++][0]; 
    } 
} 

void mergeSort(int a[][2], int len) 
{ 
    if (len > 1) 
    { 
     int mid = len/2; 
     mergeSort(a, mid); 
     mergeSort(a+mid, len-mid); // note: pointer math for right-segment 
     merge(a, mid, len); 
    } 
} 

int main() 
{ 
    int array[10][2] = {{0,55},{1,3},{2,4},{3,5},{4,6},{5,7},{6,8},{7,9},{8,10},{9,2}}; 
    int i; 
    int len = sizeof(array)/sizeof(array[0]); 
    for(i = 0 ;i < len; i++) 
     printf("%d ",array[i][1]); 

    mergeSort(array, len); 

    printf ("\nIndex after sorting:\n") ; 
    for(i = 0 ;i < len; i++) 
     printf("%d ",array[i][0]); 

    printf ("\nArray after sorting:\n") ; 
    for(i = 0 ;i < len; i++) 
     printf("%d ",array[i][1]); 
} 

輸出

55 3 4 5 6 7 8 9 10 2 
Index after sorting: 
9 1 2 3 4 5 6 7 8 0 
Array after sorting: 
2 3 4 5 6 7 8 9 10 55