Mój problem polega na tym iż porogram się sypie przy próbie użycia Merge sorta. Mam wrażenie że dla pomniejszych danych sortowanie poprzez scalanie działa prawidłowo, zaś przy większych danych program wyświetla błąd.
#include<iostream>
#include<cstdlib>
#include<time.h>
#include<windows.h>
using namespace std;
clock_t start,stop;
double czas;
void merge(int tablica[], int start, int srodek, int koniec)
{
int *tab_pom = new int[(koniec-start)]; // utworzenie tablicy pomocniczej
int i = start, j = srodek+1, k = 0; // zmienne pomocnicze
while (i <= srodek && j <= koniec)
{
if (tablica[j] < tablica[i])
{
tab_pom[k] = tablica[j];
j++;
}
else
{
tab_pom[k] = tablica[i];
i++;
}
k++;
}
if (i <= srodek)
{
while (i <= srodek)
{
tab_pom[k] = tablica[i];
i++;
k++;
}
}
else
{
while (j <= koniec)
{
tab_pom[k] = tablica[j];
j++;
k++;
}
}
for (i = 0; i <= koniec-start; i++)
tablica[start+i] = tab_pom[i];
}
void merge_sort(int tablica[], int start, int koniec)
{
int srodek;
if (start != koniec)
{
srodek = (start + koniec)/2;
merge_sort(tablica, start, srodek);
merge_sort(tablica, srodek+1, koniec);
merge(tablica, start, srodek, koniec);
}
}
void heapify (int *tab, int heap_size, int i)
{
int largest, temp;
int l=2*i, r=(2*i)+1;
if (l<=heap_size && tab[l]>tab[i])
largest=l;
else largest=i;
if (r<=heap_size && tab[r]>tab[largest])
largest=r;
if (largest!=i)
{
temp=tab[largest];
tab[largest]=tab[i];
tab[i]=temp;
heapify(tab,heap_size,largest);
}
}
void budKopiec(int *tab, int rozmiar)
{
for (int i=rozmiar/2;i>0;i--)
heapify(tab,rozmiar, i);
}
void sort(int *tab, int rozmiar)
{
int temp;
budKopiec(tab, rozmiar);
for (int i=rozmiar;i>1;i--)
{
temp=tab[i];
tab[i]=tab[1];
tab[1]=temp;
rozmiar--;
heapify(tab,rozmiar,1);
}
}
void sortowanie_babelkowe(int *tab, int n)
{
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;
}
}
}
}
int partition(int tablica[], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
int x = tablica[p]; // obieramy x
int i = p, j = r, w; // i, j - indeksy w tabeli
while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
{
while (tablica[j] > x) // dopoki elementy sa wieksze od x
j--;
while (tablica[i] < x) // dopoki elementy sa mniejsze od x
i++;
if (i < j) // zamieniamy miejscami gdy i < j
{
w = tablica[i];
tablica[i] = tablica[j];
tablica[j] = w;
i++;
j--;
}
else // gdy i >= j zwracamy j jako punkt podzialu tablicy
return j;
}
}
void quicksort(int tablica[], int p, int r) // sortowanie szybkie
{
int q;
if (p < r)
{
q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
}
}
int main()
{
const int N = 20; // liczebnoϾ zbioru
int d[N + 1],i,j,k,m,x;
int ilosc_liczb;
cout << "Podaj ilosc licz do posortowania: ";
cin >> ilosc_liczb;
int *tablica = new int [ilosc_liczb];// utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow
int *tablica2 = new int [ilosc_liczb];
int *tablica3 = new int [ilosc_liczb];
int *tablica4 = new int [ilosc_liczb];
srand(time(NULL));
for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{
tablica[i]= rand()%10000+1;
}
start= clock();
quicksort(tablica,0,ilosc_liczb-1);
stop= clock();
czas = (double)(stop-start) / CLOCKS_PER_SEC;
cout<<"Czas quicksort "<<"s "<<czas<<endl;
for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{
tablica2[i]= tablica[i];
}
start=clock();
sortowanie_babelkowe( tablica2,ilosc_liczb);
stop= clock ();
czas=(double)(stop-start)/CLOCKS_PER_SEC;
cout<<"Czas sortowania bombelkowego "<<"s "<<czas<<endl;
for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{
tablica3[i]= tablica2[i];
}
start= clock();
sort (tablica3,ilosc_liczb);
stop= clock();
czas = (double)(stop-start) / CLOCKS_PER_SEC;
cout<<"Czas kopca "<<"s "<<czas<<endl;
for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{
tablica4[i]= tablica3[i];
}
start= clock();
merge_sort(tablica4, 0,ilosc_liczb-1);
stop= clock();
czas= (double)(stop-start) / CLOCKS_PER_SEC;
cout<<"Czas Merge sorta "<<"s "<<czas<<endl;
delete [] tablica;
delete [] tablica2;
delete [] tablica3;
delete [] tablica4;// zwolnienie tablicy zaalokowanej dynamicznie
return 0;
}
