1

修正済み-テンプレートクラスでリンカーの問題が発生したため、.cppファイルも含めました-mergesort.cppでメモリリークが発生し、クイックソート（後に含まれる）も機能しなくなりました。イントロソートは以前に含まれていたので、うまくいきました。

私のqsortアルゴリズム：

#include "quicksort.h"

template <class typ> 
void quicksort(typ* tab, long int begin, long int end) {
  long int i = begin; 
  long int j = end;
  typ tmp;
  typ pivot = tab[(begin + end) / 2];

  /* podziel */
  while (i <= j) {
        while (tab[i] < pivot)
              i++;
        while (tab[j] > pivot)
              j--;
        if (i <= j) {
              tmp = tab[i];
              tab[i] = tab[j];
              tab[j] = tmp;
              i++;
              j--;
        }
  };

  /* rekurencja */
  if (begin < j)
        quicksort(tab, begin, j);
  if (i < end)
        quicksort(tab, i, end); 
}

Visual Studio 11（win 64）とdevc++を使用して2台の異なるコンピューターでこれを構築しました。同じことが私のマージソートにも起こります。32002要素とそれ以上。

マージソート：

#include "mergesort.h"

using namespace std;


template <class typ>
void merge(typ *tab, long int begin, long int mid, long int end){
 typ *tab_pom = new typ[end+1];
 long int  i,j,k;

 i=begin; //pierwsza czesc
 j=mid+1; //druga czesc
 k=0;

 while ( (i<=mid) && (j<=end) ){ //pierwsze mniej niz srodek drugie mniej niz koniec
           if(tab[i] < tab[j]){
                tab_pom[k]=tab[i];
                i++;
                k++;
           }else{
                tab_pom[k]=tab[j];                
                j++;
                k++;
           }   
 }

 if (!(i<=mid)){
      while(j<=end){  
           tab_pom[k]=tab[j];
           k++;
           j++;
      } 
 }else{

      if (!(j<=end)){
           while(i<=mid){
                tab_pom[k]=tab[i];
                k++;
                i++;
           } 
      }
 }
 k=0;
 for (i=begin;i<=end;i++){
      tab[i]=tab_pom[k];
      k++;
 }         
}


// dzieli dane az do otzrymania posortowanych tablic jedno elementowych

template <class typ>
void merge_sort(typ *tab, long int begin, long int end){
 long int mid;

 if (begin < end){
      mid=(begin+end)/2;
      merge_sort(tab,begin,mid);
      merge_sort(tab,mid+1,end);
      merge(tab,begin,mid,end);
 }    
}

イントロソートも作成しました。これは、あらゆる要素に最適です。VisualStudio11->プロジェクト->プロパティ->リンカー->スタック予約サイズ->80000000でスタックサイズを増やしてみました。何も変更されていません。助けていただければ幸いです。

ソース：

#include <iostream>
#include <time.h>
#include "introspectiv.h"
#include "introspectiv.cpp"
#include "mergesort.h"
#include "mergesort.cpp"
#include "quicksort.h"
#include "quicksort.cpp"

using namespace std;

//funkcja do kopiowania tablicy 
template<class typ>
void kopiuj(typ* tabl_1, typ* tabl_2, int indeks){
for (int i = 0 ; i < indeks ; i++) tabl_2[i] = tabl_1[i];
}

int main() {
//tworzy tablice
cout << "podaj rozmiary tablicy wypelnionej losowymi liczbami: ";
int wybor;
clock_t czas[7];
clock_t start, stop;
long int n, i, end, begin;
cin >> n;
int *tablica = new int[n];
int *tab_pom = new int[n];
for (i=0; i<n; i++){
    tablica[i] = rand() % 100;
}

end = n-1;
begin = 0;

float procent[] = {0, 0.25, 0.5, 0.75, 0.95, 0.99, 0.997};

cout << endl << "wybierz algorytm sortowania: " << endl;
cout << "quicksort - 1 " << endl;
cout << "mergesort - 2 " << endl;
cout << "introspektywne - 3 " << endl;
cin >> wybor;
switch (wybor)
{
case 1: {
    for (i=0; i<7; i++){
        kopiuj(tablica, tab_pom, end);
        end = end*procent[i]; 
        quicksort(tab_pom, begin , end);

        end = n-1;
        start=clock();
        quicksort(tab_pom, begin , end);
        stop=clock();  
        czas[i] = stop-start;

            }
        }

case 2: {
    start=clock();  
    merge_sort(tablica, begin , end);
    stop=clock();
        }
case 3: {
    start=clock();
    introspective(tablica, n);
    stop=clock();
        }
default: break;
    }


//for (i=0; i<n; i++){
//  cout<<tablica[i]<< " ";
//}

cout << endl << "Czas wybranego sortowania: " << endl; 

for (i=0; i<7; i++){
cout << "Dla " << procent[i]*100 << "% posortowanych danych: " << czas[i] << " ms"    << endl << endl;
}
system("pause");
}

イントロとマージソートで時間をカウントするために終了していません。

4

1 に答える 1

3

クイックソート：32000要素の場合、クイックソートは再帰の深さが約15であるため、スタックサイズについて心配する必要はありません。問題は、渡そうとしているオブジェクトが関数内のローカル変数であるため、サイズが制限されていることである可能性があります。グローバル変数または静的変数として割り当ててみてください。例：

void myfunction(){
    static int myelements[40000];
    //...
    merge_sort(myelements, 0, sizeof(myelements)/sizeof(int));
    //....
}

マージソート：新しいものを何度も呼び出しているようですが、削除はありません。とにかくメモリを割り当てる必要がある理由がわかりません。代わりにポインタを使用できます。追加してみてください

delete[] tab_pom;

マージの終了時。

次回は、機能しないよりも少し多くの診断の助けを与えるようにしてください。おそらくエラーメッセージ。乾杯、お役に立てば幸いです。

于 2012-04-20T12:53:37.050 に答える