Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти точку между зарядами, где равнодействующая равна 0 http://www.cyberforum.ru/cpp-beginners/thread1164470.html
Доброго времени суток, заседатели форума. У меня возникла проблема с этой задачей. Вы не могли-бы мне с ней помочь? Условие прилагаю: На прямой находятся 3 положительных заряда величины q1,q2,q3,...
C++ Возврат к началу switch Здравствуйте. Есть программа, включающая в себя ... switch(x) { case 1: {}; case 2: {}; case n: {}; default: {}; http://www.cyberforum.ru/cpp-beginners/thread1164463.html
C++ Изменение размера созданного вектора
Как изменить размер вектора? Например, проводим какие-нибудь вычисления и результатов получилось больше, чем размер вектора. Как в таком случаи увеличить вектор?
Проверить список запущенных процессов на наличие нужного C++
Задача: 1. Все просто - проверить список запущенных процессов на наличие нужного мне процесса , если найден возвращаем правду если не найден выходим , ВНИМАНИЕ!!! функцию нужно вызывать постоянно ,...
C++ Sublime text 2 + MinGW не получается настроить http://www.cyberforum.ru/cpp-beginners/thread1164443.html
Все делал по теме: http://www.cyberforum.ru/blogs/390663/blog1982.html Или этот способ не подходит для Sublime text 2? Нажимаю Ctrl+B или Ctrl+Shift+B ничего не происходит, только появляется пустая...
C++ Задать определенное число итераций Здравствуйте! Сижу и пытаюсь разбираться с методами оптимизации, алгоритмы осилила, теперь новая проблема, мне метод необходимо "прогнать" определенное число раз и тот ответ, что получу вывести. Не... подробнее

Показать сообщение отдельно
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248

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

02.05.2014, 23:09. Просмотров 424. Ответов 2
Метки (Все метки)

не могу понять куда счетчики:сравнения и обменов.помогите пожалуйста.
вот код сортировки:
C++ (Qt)
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
template<class T> void SiftDown(T* const heap, int i, int const n)
{   //Просеивает элемент номер i вниз в пирамиде heap.
     //n -- размер пирамиды
 
    //Идея в том, что вычисляется максимальный элемент из трёх:
     //  1) текущий элемент
    //  2) левый потомок
    //  3) правый потомок
    //Если индекс текущего элемента не равен индексу максималь-
    //  ного, то меняю их местами, и перехожу к максимальному
 
    //Индекс максимального элемента в текущей тройке элементов:
     int nMax( i );
     //Значение текущего элемента (не меняется):
     T const value( heap[i] );
       
     while ( true )
     { //Рассматривается элемент i и его потомки i*2+1 и i*2+2
       //В начале каждой итерации nMax == i и value == heap[i]
 
         int childN( i*2+1 ); //Индекс левого потомка
        //Если есть левый потомок и он больше текущего элемента,
         if ( ( childN < n ) && ( heap[childN] > value      ) )
             nMax = childN; //  то он считается максимальным
            
         ++childN; //Индекс правого потомка
        //Если есть правый потомок и он больше максимального,
         if ( ( childN < n ) && ( heap[childN] > heap[nMax] ) )
             nMax = childN; //  то он считается максимальным
 
        //Если текущий элемент является максимальным из трёх
        //  (т.е. если он больше своих детей), то конец:
         if ( nMax == i ) break;
         
         //Меняю местами текущий элемент с максимальным:
         heap[i] = heap[nMax]; heap[nMax] = value; 
         //  при этом значение value будет в ячейке nMax,
         //  поэтому в начале следующей итерации значение value
         //  правильно, т.к. мы переходим именно к этой ячейке
 
        //Переходим к изменившемуся потомку
        i = nMax;
 
     };
}
template<class T> void HeapSort(T* const heap, int n)
{   //Пирамидальная сортировка массива heap.
     //  n -- размер массива
  
     //Этап 1: построение пирамиды из массива
    for(int i(n/2-1); i>=0; --i) SiftDown(heap, i, n);
     
     //Этап 2: сортировка с помощью пирамиды.
     //  Здесь под «n» понимается размер пирамиды
    while( n > 1 ) //Пока в пирамиде больше одного элемента
    {
         --n; //Отделяю последний элемент
 
        //Меняю местами корневой элемент и отделённый:
         T const firstElem( heap[0] );
         heap[0] = heap[n];
         heap[n] = firstElem;
         
         //Просеиваю новый корневой элемент:
         SiftDown(heap, 0, n);
     }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru