I tried to program a version of this algorithm, however, firstly, i got some heap problems regarding writting after the buffer. Now simply while compiling i get this warning about a breakpoint being trigerred :(
#include <iostream> // cout
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
using namespace std;
int MergeandCountSplitInversions( int * tablica, int poczatek, int koniec, int dlugosc);
int SortandCountArray ( int * tablica, int poczatek, int koniec, int dlugosc)
{
if (dlugosc==1) return 0;
else
{
if(dlugosc%2==0)
{
int x=SortandCountArray(tablica, poczatek, poczatek+dlugosc/2-1 ,dlugosc/2);
int y=SortandCountArray(tablica, poczatek+dlugosc/2, koniec ,dlugosc/2);
int z=MergeandCountSplitInversions(tablica,poczatek,koniec,dlugosc);
return x+y+z;
}
else
{
int x=SortandCountArray(tablica, poczatek, poczatek+((dlugosc+1)/2)-1 ,(dlugosc+1)/2);
int y=SortandCountArray(tablica, poczatek+((dlugosc+1)/2), koniec ,(dlugosc+1)/2-1);
int z=MergeandCountSplitInversions(tablica,poczatek,koniec,dlugosc);
return x+y+z;
}
}
}
int MergeandCountSplitInversions( int * tablica, int poczatek, int koniec, int dlugosc)
{if (dlugosc==1) return 0;
else
{
int licznik=0;
int * wynik= new int[dlugosc];
if(dlugosc%2==0)
{int j=poczatek,k=poczatek+dlugosc/2, l;
int main()
{
int i;
int rozmiar=rand()%1000;
int * tablica=new int[rozmiar];
for(i=0;i<rozmiar;i++)
tablica[i]=rand()%1000;
cout << SortandCountArray(tablica, 0, rozmiar-1, rozmiar);
getchar();
getchar();
delete [] tablica;
return 0;
}
Any ideas what went wrong ???
Also i owe you some explanations (translations)
poczatek means beginning
koniec means ending
dlugosc means length
rozmiar means size
tablica means array