Подскажите, как наиболее точно оценить число перестановок в HeapSort?
Алгоритм тот же, что и в разделе http://forum.vingrad.ru/forum/topic-37776/anchor-entry285335/15.html:
| Код |
//=======================HeapSort================================================
template <class Type> void heap_sort(Type *a, unsigned long n, unsigned long& move, unsigned long& srav){
Type x;
unsigned long left = n/2, right = n-1;
while(left>0){//Формирование пирамиды
left--;
sift(a,left,n-1,move,srav);
}
while(right>0){//формирование упорядоченного массива
move++; //перестановка ( или тут надо +2? +3?)
x = a[0];
a[0] = a[right];
a[right] = x;
right--;
sift(a,0,right,move,srav);
}
}
//=======================Sift======================================================
template <class Type> void sift(Type *a, unsigned long left, unsigned long right, unsigned long& move, unsigned long& srav){
unsigned long i = left, j = 2*left+1;
Type x, elem = a[left];
srav++; // увеличивается счётчик сравнений
if(j<right && a[j]<a[j+1]) j++;
while(j<=right && elem<a[j]){
move++; // перестановка ( или тут надо +2? +3? )
x = a[i];
a[i] = a[j];
a[j] = x;
i = j;
elem = a[i];
j = 2*j+1;
srav++; // увеличивается счётчик сравнений
if(j<right && a[j]<a[j+1]) j++;
}
}
|
|