Witam mam taki problem z implementacja Algorytmu sortowania przez scalanie. Otóż piszę program przyrównujący czas sortowania wybranych przeze mnie algorytmów sortowania dla identycznej liczby n
wszystko działa fajnie do momentu przyłączenia się do tego programu algorytmu sortowania przez scalanie .
UWAGA KOD JEST DŁUGI
#include <iostream>
using namespace std;
#include <time.h>
#include <windows.h>
#include <iomanip>
int ile;
clock_t start,stop;
double czas;
void sortowanie_babelkowe(int *tab,int n) //ok
{
for(int i=1;i<n;i++)
{
for(int j=n-1;j>=1;j--)
{
if(tab[j]>tab[j-1])
{
int bufor;
bufor=tab[j-1];
tab[j-1]=tab[j];
tab[j]=bufor;
}
}
}
}
void quicksort(int *tablica, int lewy, int prawy) //ok
{
int v=tablica[(lewy+prawy)/2];
int i,j,x;
i=lewy;
j=prawy;
do{
while (tablica[i]>v) i++;
while (tablica[j]<v) j--;
if (i<=j){
x=tablica[i];
tablica[i]=tablica[j];
tablica[j]=x;
i++; j--;
}
}while (i<=j);
if (j>lewy) quicksort(tablica,lewy, j);
if (i<prawy) quicksort(tablica, i, prawy);
}
void Selection( int *tablica11, int size ) //ok
{
int k;
for( int i = 0; i < size; i++ )
{
k = i;
for( int j = i + 1; j < size; j++ )
if( tablica11[ j ] > tablica11[ k ] )
k = j;
swap( tablica11[ k ], tablica11[ i ] );
}
}
void Insertion( int *tablica111, int size ) //ok
{
int temp, j;
for( int i = 1; i < size; i++ )
{
temp = tablica111[ i ];
for( j = i - 1; j >= 0 && tablica111[ j ] < temp; j-- )
tablica111[ j + 1 ] = tablica111[ j ];
tablica111[ j + 1 ] = temp;
}
}
int *pom; //tablica pomocnicza, potrzebna przy scalaniu
//scalenie posortowanych podtablic
void scal(int *tablica555, int lewy, int srodek, int prawy)
{
int i = lewy, j = srodek + 1;
//kopiujemy lewą i prawą część tablicy do tablicy pomocniczej
for(int i = lewy;i<=prawy; i++)
pom[i] = tablica555[i];
//scalenie dwóch podtablic pomocniczych i zapisanie ich
//we własciwej tablicy
for(int k=lewy;k<=prawy;k++)
if(i<=srodek)
if(j <= prawy)
if(pom[j]<pom[i])
tablica555[k] = pom[j++];
else
tablica555[k] = pom[i++];
else
tablica555[k] = pom[i++];
else
tablica555[k] = pom[j++];
}
void sortowanie_przez_scalanie(int *tablica666,int lewy, int prawy)
{
//gdy mamy jeden element, to jest on już posortowany
if(prawy<=lewy) return;
//znajdujemy srodek podtablicy
int srodek = (prawy+lewy)/2;
//dzielimy tablice na częsć lewą i prawa
sortowanie_przez_scalanie(tablica666, lewy, srodek);
sortowanie_przez_scalanie(tablica666, srodek+1, prawy);
//scalamy dwie już posortowane tablice
scal(tablica666, lewy, srodek, prawy);
}
int main()
{
cout<<"Porownanie czasow sortowanie"<<endl;
cout<<"ile losobywch liczb w tablicy";
cin>>ile;
//dynamiczne alokowanie tablicy
int*tablica;
tablica=new int[ile];
int*tablica2;
tablica2=new int[ile];
int *tablica3;
tablica3=new int[ile];
int *tablica4;
tablica4=new int[ile];
int *tablica5;
tablica5=new int[ile];
int *tablica6;
tablica6=new int [ile];
//genetator
srand(time(NULL));
//wczytywanie generatora
for(int i=0;i<ile;i++)
{
tablica[i]=rand()%100000+1;
}
//przepisanie tablicy do tablicy2
for(int i=0;i<ile;i++)
{
tablica2[i]=tablica[i];
}
for(int i=0;i<ile;i++)
{
tablica3[i]=tablica[i];
}
for(int i=0;i<ile;i++)
{
tablica4[i]=tablica[i];
}
for(int i=0;i<ile;i++)
{
tablica5[i]=tablica[i];
}
for(int i=0;i<ile;i++)
{
tablica6[i]=tablica[i];
}
/*
cout<<"PRZED SORTOWANIEM:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica[i]<<" ";
}
*/
cout<<"sortuje teraz Algorytmem babelkowym czekac!"<<endl;
start=clock();
sortowanie_babelkowe(tablica,ile);
stop=clock();
cout<< setprecision(2);
czas=(double)(stop-start)/CLOCKS_PER_SEC;
/*
cout<<"Po SORTOWANIU:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica[i]<<" ";
}
*/
cout<<"CZAS SORTOWANIA algorytmu babelkowego:"<<czas<<"s"<<endl;
/* cout<<"PRZED SORTOWANIEM:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica2[i]<<" ";
}
*/
cout<<"sortuje teraz algorytmem QuickSort czekac!"<<endl;
start=clock();
quicksort(tablica2,0,ile-1);
stop=clock();
cout<< setprecision(2);
czas=(double)(stop-start)/CLOCKS_PER_SEC;
/*
cout<<"PO SORTOWANIU:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica2[i]<<" ";
}
*/
cout<<"CZAS SORTOWANIA algorytmu QUICKSORT:"<<czas<<"s"<<endl;
/* cout<<"PRZED SORTOWANIEM:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica3[i]<<" ";
}
*/
cout<<"sortuje teraz algorytmem SELECTION czekac!"<<endl;
start=clock();
Selection(tablica3,ile);
stop=clock();
cout<< setprecision(2);
czas=(double)(stop-start)/CLOCKS_PER_SEC;
/*
cout<<"PO SORTOWANIU:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica3[i]<<" ";
}
*/
cout<<"CZAS SORTOWANIA algorytmu SELECTION:"<<czas<<"s"<<endl;
/* cout<<"PRZED SORTOWANIEM:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica4[i]<<" ";
}
*/
cout<<"sortuje teraz algorytmem INSERTION czekac!"<<endl;
start=clock();
Insertion(tablica4,ile);
stop=clock();
cout<< setprecision(2);
czas=(double)(stop-start)/CLOCKS_PER_SEC;
/*
cout<<"PO SORTOWANIU:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica4[i]<<" ";
}
*/
cout<<"CZAS SORTOWANIA algorytmu INSERTION:"<<czas<<"s"<<endl;
/*
cout<<"PRZED SORTOWANIEM:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica[i]<<" ";
}
*/
cout<<"sortuje teraz Algorytmem SCALANIA czekac!"<<endl;
start=clock();
sortowanie_przez_scalanie(tablica6,0,ile-1);
stop=clock();
cout<< setprecision(2);
czas=(double)(stop-start)/CLOCKS_PER_SEC;
/*
cout<<"Po SORTOWANIU:"<<endl;
for(int i=0;i<ile;i++)
{
cout<<tablica[i]<<" ";
}
*/
cout<<"CZAS SORTOWANIA algorytmu SCALANIA:"<<czas<<"s"<<endl;
delete[] tablica;
delete[] tablica2;
delete[] tablica3;
delete[] tablica4;
delete[] tablica5;
system("pause");
return 0;
}