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?