VPF::число сравнений и "пересылок" в HeapSort

Avaj

Дата 12.10.2008, 13:09 (ссылка)

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

Загрузка ...

Бывалый

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

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

Я уже обращался с аналогичным вопросом,Akina мне ответил - спасибо ему, но возникли некоторые недоразумения.

Как уже говорилось мне нужно было посчитать кол-во обменов в сортировке Бинарными вставками и в Heapsort. Но как выяснилось в Бин.встав. обменов не происходит smile

, там происходит нечто другое, назовём это "пересылками". (или есть некое более подходящее название?)

Так вот первый вопрос: правильно ли я считаю сравнения и эти самые "пересылки" в своей ф-ции?

Код


template <class Type> void bin_ins(Type *a, unsigned long n, unsigned long& move, unsigned long& srav){
    Type x;    
    unsigned long left, right, m, j, i;
    for(i=1;i<n;i++){
        x = a[i];
        left = 0;
        right = i;
        while(left<right){
            m = (left+right)/2;       
            if(a[m]<=x) left = m+1;
             srav++;   // тут счётчик сравнений должен увеличиваться?
            else right = m;
        }
        for(j=i;j>right;j--){
            a[j] = a[j-1];//а тут как я понимаю происходят эти самые "пересылки"?
            move++;
        }
        a[right] = x;   // и тут тоже?
        move++;
    }
}

Поясняю:

a - сортируемый массив

n - его размерность

move - число "пересылок"

srav - число сравнений.

И второй вопрос.

Т.к. мне нужно сравнить метод Бин.встав. и HeapSort по числу сранений и этих самых "пересылок", то правильно ли я их считаю в ф-циях для HeapSort?

Код


//=======================Sort================================================
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+=3; // нужно ли здесь увеличивать число "пересылок" на 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+=4;   // а здесь на сколько надо увеличивать кол-во "пересылок"?
        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 - 12.10.2008, 14:31

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