修正済み-テンプレートクラスでリンカーの問題が発生したため、.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");
}
イントロとマージソートで時間をカウントするために終了していません。