Merge sort.

0

Witam, próbuje sam zaimplementować sortowanie przez scalanie, niestety gdzieś robię błąd.

void merge(int *tab, int p, int mid, int k)
{
	//p,k - granice sortowanej aktulnie podtablicy
	//mid - srodek tablicy, granica kazdej z podtablic przy podziale na pol

	//jedna tablica od p do mid, druga od mid do k

	int *tmp = new int[k-p+1];

	int i=p, j=mid+1; //iteratory dla pierwszej i drugiej czesci tablicy
	int m=0; //iterator dla tablicy pomocniczej
	
	//mid - p rozmiar 1. tab
	//k - mid rozmiar 2. tab
	
	while (i!=mid+1 && j!=k+1) //iterator dochodzi do ostatniego elementu w jednej z tablic
	{
		if (tab[i]<tab[j])	tmp[m++]=tab[i++];
		else tmp[m++]=tab[j++];
	}

	if (i==mid && j==k) for (int l=p, m=0; l<k+1; l++, m++) tab[l]=tmp[m];
	if (i==mid+1) for (j; j<k+1; j++, m++) tmp[m]=tab[j];
	else if (j==k+1) for(i; i<mid+1; i++, m++) tmp[m]=tab[i];

	for(int jk=0; jk<k-p+1; jk++) cout<<tmp[jk]<<' ';
	cout<<"\n";

	for (int l=p, m=0; l<=k+1; l++, m++) tab[l]=tmp[m]; //spisujemy dane posortowane z tablicy pomocniczej
	//delete tmp;

	return;
}

void mergeSort(int *tab, int p, int k)
{
	int mid=(p+k)/2;
	
	if(p!=k)
	{
		mergeSort(tab, p, mid); //sortujemy lewa czesc tablicy
		mergeSort(tab, mid+1, k); //sortujemy prawa czesc tablicy
		merge(tab, p, mid, k); //scalamy posortowane czesci
	}
	return;
}

Przy próbie sortowania tablicy większej niż dwuelementowa dostaję trochę śmieci z pamięci i część posortowanej tablicy. Gdzie mogłem zrobić błąd?

0

Problem rozwiązany:P Błąd był banalny ale takie zawsze najtrudniejsze do znalezienia:)

for (int l=p, m=0; l<=k+1; l++, m++) tab[l]=tmp[m]; //spisujemy dane posortowane z tablicy pomocniczej 

W tym miejscu spisuję część danych z tablicy pomocniczej do głównej, część która jest posortowana. Tutaj spisuję o jeden element za dużo

l<=k+1 

i jest nim właśnie śmieć z pamięci jako, że tablica nie jest wyzerowana:) Może komuś w dalekiej przyszłości to zaoszczędzi trochę nerwów.

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