合併排序做出錯誤的答案

我想實現合併排序，這是我的代碼：合併排序做出錯誤的答案

#include <stdio.h> 
#include <stdlib.h> 
#include <iostream> 
#include <fstream> 
using namespace std; 
void merge_inplace (int *elem , int *axu, int lo, int mid, int hi) 
{ 
    int i =lo; 
    int j= mid +1; 
    for (int k=lo;k<hi; k++) 
    { 
     axu[k]=elem[k]; 
    } 
    for(int k=lo; k<hi;k++) 
    { 
     if(i> mid) 
      elem[k]=axu[i++]; 
     else if(j> hi) 
      elem[k]=axu[j++]; 
     else if (axu[i]<axu[j]) 
      elem[k]= axu[i++]; 
     else elem[k]= axu[j++]; 
    } 
} 

void mergesort(int *elem ,int *axu, int lo,int hi) 
{ 
    if(hi<=lo) return; 
    int mid = lo + (hi-lo)/2; 
    mergesort(elem,axu, lo, mid); 
    mergesort(elem,axu, mid+1,hi); 
    merge_inplace(elem,axu,lo, mid, hi); 
} 

int main() 
{ 
    ifstream in_file ; 
    ofstream out_file; 
    int size =0; 
    int element; 
    int* elem; 
    in_file.open("in_file.txt"); 
    if (!in_file)perror ("Error openning file"); 


    in_file >> size; 
    elem = new int[size]; 

    for (int i=0; i<size;i++) 
    { 
     in_file >> elem[i]; 
    } 

    int * axu = new int [size]; 
    mergesort (elem,axu,0,size-1); 

    out_file.open("out_file.txt"); 

    if (out_file.fail()) 
    { 
     printf("Error opening file for output.\n"); 

     return 0; 
    } 
    for (int i=0; i < size; i++) 
    { 
     out_file << elem[i]; 
    } 
    out_file.close(); 
    return 0; 
}

的出「out_file.txt」把程序是這樣的：

-842150451-842150451-842150451-842150451-842150451-842150451-33686019-1414812757-84215045110

調試後，我發現，當合並函數返回元素的數組會破壞和馬柯值錯誤

我的輸入文件含有（每行一個整數）：

來源

2013-08-23 Farzad Salimi Jazi

我假設你需要實現自己的合併算法，因爲如果不是，你瘋了不只是使用['std :: inla ce_merge（）']（http://en.cppreference.com/w/cpp/algorithm/inplace_merge）。（這是我認爲你的問題在哪裏，順便說一句，你的合併算法，但我沒有時間去剖析它）。 – WhozCraig

我不知道inplace_merge（），感謝這短暫的時間:)對於我來說，我想知道我的指針問題，我已經根據sodu代碼實現了它。 –

更新您的問題以包含輸入文件的內容。有些東西可以讓人生活可愛。 – WhozCraig

上合併排序&轉移一些錯誤輔助初始化合並排序功能

#include <stdio.h> 
#include <stdlib.h> 
#include <iostream> 
#include <fstream> 
using namespace std; 
void merge_inplace (int *elem , int *axu, int lo, int mid, int hi) 
{ 

    int i =lo; 
    int j= mid +1; 
    for (int k=0;k<=hi; k++) // <------------- transfer initialization into the merge 
    { 
     axu[k]=elem[k]; 
    } 
    for(int k=lo; k<=hi;k++) 
    { 
     if(i> mid) 
      elem[k]=axu[j++]; // <----------------- i<--->j 
     else if(j> hi) 
      elem[k]=axu[i++]; // <------------------ i<--->j 
     else if (axu[i]<axu[j]) 
      elem[k]= axu[i++]; 
     else elem[k]= axu[j++]; 
    } 
} 
void mergesort_book(int *elem ,int *axu, int lo,int hi) 
{ 
    if(hi<=lo) return; 
    int mid = lo + (hi-lo)/2; 
    mergesort_book(elem,axu, lo, mid); 
    mergesort_book(elem,axu, mid+1,hi); 
    merge_inplace(elem,axu,lo, mid, hi); 
} 
//static void merge(vector <int> elements,) 
int main() 
{ 
     ifstream in_file ; 
     ofstream out_file; 
     int size =0; 
     int element; 
     int* elem; 
     in_file.open("in_file.txt"); 
     if (!in_file)perror ("Error openning file"); 


        in_file >> size; 
        elem = new int[size]; 

     for (int i=0; i<size;i++) 
     { 
      in_file >> elem[i]; 
     } 

     int * axu = new int [size]; 

     mergesort_book (elem,axu,0,size-1); 

     out_file.open("out_file.txt");   

    if (out_file.fail())   
    { 
     printf("Error opening file for output.\n"); 

     return 0; 
    } 
     for (int i=0 ; i < size; i++) 
     { 
      //out_file << elem[i]; 
      printf("%d\n", elem[i]); 
     } 
     out_file.close(); 
return 0; 
}

來源

2013-08-24 15:03:58

合併排序做出錯誤的答案

回答

相關問題