Форум программистов, компьютерный форум CyberForum.ru

Пирамидальная сортировка - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Метод принятия решения в консоле http://www.cyberforum.ru/cpp-beginners/thread306052.html
Уважаемые форумчане помогите реализовать задание в программном коде.Суть задания в консоле сравнить 3 моб.телефона,по 5 функциям,выставить оценку от 1 до 3,и в конце последней поставленой циферки посчитать и вывести какой телефон набрал больше баллов,Помогите,пожалуйста,Заранее спасибо
C++ преобразовать код Как будет выглядит такой код на Паскале ? Помогите! #include <iostream.h> #include <stdio.h> #include <stdlib.h> #include <conio.h> int vpor(int *a, int m) { int x,i,j; http://www.cyberforum.ru/cpp-beginners/thread306028.html
Что значит? C++
std::cout << (myCircle.pointInCircle(x, y) ? "In circle" : "Out of circle"); Что означет эта строчка?
C++ Объясните sizeof()
Вопрос, скажите для чего можно использовать sizeof()?
C++ Сформулировать вектор из произведения элементов столбцов и найти их среднее арифметическое http://www.cyberforum.ru/cpp-beginners/thread305998.html
Сформировать вектор из произведения элементов столбцов и найти их среднее арифметическое
C++ Сформулировать вектор из наименьших значений элементов строк и найти их среднее арифметическое Сформировать вектор из наименьших значений элементов строк и найти их среднее арифметическое подробнее

Показать сообщение отдельно
Extro
0 / 0 / 0
Регистрация: 11.06.2012
Сообщений: 31
13.11.2012, 08:48     Пирамидальная сортировка
Доброго времени суток.
Есть у меня такой код пирамидальной сортировки
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void pyramid(){ 
    int sh = 0; //смещение
    bool b = false;
    while(1){
        b = false;
        for ( int i = 0; i < RazmerMass; i++ ){
            if( i * 2 + 2 + sh < RazmerMass ){
                KolvSravn++;
                if( ( mass[i + sh] > mass[i * 2 + 1 + sh] ) || ( mass[i + sh] >  mass[i * 2 + 2 + sh])){
                    KolvSravn++;
                    if ( mass[i * 2 + 1 + sh] <  mass[i * 2 + 2 + sh] ){
                         KolvPeres++;
                        swap( mass[i + sh], mass[i * 2 + 1 + sh] );
                        b = true;
                    }
                    else {KolvSravn++;
                         if ( mass[i * 2 + 2 + sh] < mass[ i * 2 + 1 + sh]){
                         KolvPeres++;
                             swap( mass[ i + sh], mass[i * 2 + 2 + sh]);
                             b = true;
                         }
                    }    
                }
                KolvSravn++;
                    if( mass[i*2 + 2 + sh] < mass[i*2 + 1 + sh] ){
                        KolvPeres++;
                        swap( mass[i*2+1+sh], mass[i * 2 +2+ sh] );
                        b = true;
                        }
            }
            else if( i * 2 + 1 + sh < RazmerMass ){
                       KolvSravn++;
                     if( mass[i + sh] > mass[ i * 2 + 1 + sh] ){
                         KolvPeres++;
                         swap( mass[i + sh], mass[i * 2 + 1 + sh] );
                         b = true;
                     }
                 }
        }
        if (!b) sh++; 
        
        if ( sh + 2 == RazmerMass ) break; 
    } 
}
где
RazmerMass - количество элементов в массиве,
mass[] - собственно сам массив
KolvSravn - количество сравнений элементво
KolvPeres - количество пересылок элементов
Сортирует нормально. Но, по определению его сложность Θ(n log n) при любых условиях.
На случайном не отсортированном массиве в 200 элементов:
KolvSravn = 32659
KolvPeres = 2917
На том же, но отсортированном массиве:
KolvSravn = 19899
Может, у меня не так стоят счетчики сравнений/пересылок, почему я не могу увидеть сложность 200 * log 200 = 460?
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru