VPF::Оценка числа перестановок в HeapSort

Avaj

Дата 14.10.2008, 15:54 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 212
Регистрация: 14.7.2008
Где: Владивосток.

Репутация: нет
Всего: 3

Подскажите, как наиболее точно оценить число перестановок в HeapSort?

Алгоритм тот же, что и в разделе "Коллекция алгоритмов от Johna Smith":

Код


//=======================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++;
     }
}

Это сообщение отредактировал(а) Avaj - 17.10.2008, 13:13

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »