Segregowanie przez scalanie - Stack overflow

0

Czesc,
mam taki prosty programik:

#include <iostream>
#include <ctime>
#include <cstdlib>
void sc(int *tab,int  p,int  q,int  r);
void dz(int* tab, int p, int q);
int main()
{
	using namespace std;
	srand(time(NULL));
	int tab[10];
	for (int i = 0; i < 10; i++)
	{
		tab[i] = rand() % 100 + 1;
	}
	for (int i = 0; i < 10; i++)
		cout << tab[i]<<endl;
	cout << '\n';
	int* p = tab;
	dz(p, 0, 9);
	for (int i = 0; i < 10; i++)
		cout << tab[i] << endl;

}
void sc(int* tab, int  p, int  q, int  r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int* pom1 = new int[n1+1];
	int* pom2 = new int[n2+1];

	int i, j;
	for (i = 0; i < n1; i++)
		pom1[i] = tab[p + i];
	for (j = 0; j < n2; j++)
		pom2[j] = tab[q + j + 1];
	j = 0;
	i = 0;
	pom1[n1] = sizeof(int);
	pom2[n2] = sizeof(int);
	for (int k = p; k < r + 1; k++)
	{
		if (pom1[i] < pom2[j])
		{
			tab[k] = pom1[i];
			i++;
		}
		else
		{
			tab[k] = pom2[j];
			j++;
		}
	}
	delete[]pom1;
	delete[]pom2;
}
void dz(int* tab, int p, int q)
{
	if (p < q)
	{
		int n = int((q - p) / 2);
		dz(tab, p, n);
		dz(tab, n+1, q);
		sc(tab, p, n, q);
	}
}
	

niestety, po odpaleniu wyswietlaja sie liczby przed operacja segregowania po czym program konczy swoje dzialanie wraz z komunikatem:
Nieobsłużony wyjątek w lokalizacji 0x00A52519 w ConsoleApplication2.exe: 0xC00000FD: Stack overflow (parametry: 0x00000001, 0x00A72FA4).
Ktos wie moze jak sobie z tym poradzic?

1

zakoduj to w C++ a nie w C (tak teraz to wygląda) używając std::vector.
Odpadnie ci zarządzanie pamięcią i łatwiej będzie ogarnąć co i jak.

1

Gdzieś w odmętach rekurencji wywołana zostaje funkcja

sc(tab, 3, 0, 4); 

co prowadzi do definicji tablicy pom1 o ujemnym wymiarze.

Dodatkowo wywołanie

dz(tab, 2, 4);

prowadzi do wywołania

dz(tab, 2, 1); // to się skończy
dz(tab, 2, 4); // to doprowadza do niekończącej się rekurencji i w efekcie do wysypania się programu
1

Gdzieś wpadasz w nieskończoną rekurencje wołając te swoje dz. Wypisuj indeksy z którymi tam wchodzisz i zobaczysz gdzie się to dzieje.

0

Okej,
program konczy dzialanie gdy
sc(tab, 0, 0, 1)

jednak nie wiem jak to naprawic :/

1

Zobacz jak to jest zrobione na tej stronie https://www.geeksforgeeks.org/merge-sort/

0

Pieknie dziekuje, wystarczyla zmiana na:
int n = (p + (q - 1)) / 2;

1 użytkowników online, w tym zalogowanych: 0, gości: 1