Сбой алгоритма сортировки кучи C ++ после 4100+ записей данных?

Я разработал следующий код алгоритма сортировки кучи, но по какой-то причине он прекрасно работает до определенного момента (около 4100 регионов), после чего программа вынуждена закрываться?

Любая помощь будет принята с благодарностью, спасибо.

void heap_from_root(MVector &v, int i, int n) {

int end=n,j=0;

// Identify the lowest root and how many sons it has. If it only has one son, set j=1.
if (n==1) { n = 0; j = 1; }
else if ((n-2) % 2 == 0) { n = (n-2)/2; }
else if ((n-1) % 2 == 0) { n = (n-1)/2; j=1; }

while (i <= n) { // Start from the lowest root, and go up until the highest root.

if (j==0) { // If 2 sons, then check for the biggest value. If the biggest value is greater than root, exchange.

if (v[2*n+1] > v[2*n+2] && v[2*n+1] > v[n]) { v.swap(2*n+1,n); }
if (v[2*n+2] > v[2*n+1] && v[2*n+2] > v[n]) { v.swap(2*n+2,n); }

}

if (j==1) { // If 1 son, if the son's value is greater than the root, exchange.

if (v[2*n+1] > v[n]) { v.swap(2*n+1,n); }
j=0; // As only the last root can only have one son, set j to 0.

}

n--; // Go backwards to the next root.

}

/* The top value of the heap will now be the biggest value. If the heap hasn't been completed sorted,
put the biggest value at the END of the heap, and restart the algorithm, this time excluding that last
value. Repeating this recursively will mean the heap will be sorted in ascending order. This saves using
significant excess memory. */

if (i < end) { v.swap(i,end); end--; heap_from_root(v,i,end); }

}

void heap(MVector &v) { heap_from_root(v,0,v.size()-1); }

Класс MVector — это:

// class MVector contains arrays that can work with doubles
class MVector
{
// storage for the new vector class
vector<double> v;
public:
// constructor
explicit MVector(){}
explicit MVector(int n):v(n){srand(static_cast<unsigned>(time(NULL)));}
explicit MVector(int n,double x):v(n,x){}
// equate vectors;
MVector& operator=(const MVector& X)
{if(&X==this)return *this;v=X.v;return *this;}
// access data in vector
double& operator[](int index){ return v[index]; }
// access data in vector (const)
double operator[](int index) const { return v[index]; }
// size of vector
int size() const {return v.size();}
void push_back(double x){v.push_back(x);}
void swap(int i,int j) { double c; c=v[i]; v[i] = v[j]; v[j] = c;  }
void initialise_random(double xmin, double xmax) {
const unsigned n = this->size();
for(unsigned i=0;i<n;i++) {
v[i] = xmin + rand()*(xmax - xmin) / static_cast<double>(RAND_MAX);
}
}

bool cmp(int i, int j) {
if (v[i] < v[j]) { return true; }
else { return false; }
}
}; // end class MVector

И его инициируют с

int main ()
{
MVector x(4500);
x.initialise_random(0,10);
double y0 = timer();
Sort::heap(x);
double y = timer();

std::cout << abs(y-y0) << endl;
}

0

Решение

Не ответ, а наблюдение. У вас есть этот код:

if (n==1) { n = 0; j = 1; }
else if ((n-2) % 2 == 0) { n = (n-2)/2; }
else if ((n-1) % 2 == 0) { n = (n-1)/2; j=1; }

Учтите, что когда n странно, n/2 == (n-1)/2, И когда n даже, (n-1)/2 == (n-2)/2, Таким образом, вы можете заменить весь этот код на:

if ((n % 2) == 1) { j = 1; }
n = (n-1)/2;
1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]