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

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

Восстановить пароль Регистрация
 
Gmails
5 / 5 / 2
Регистрация: 08.04.2014
Сообщений: 241
02.05.2014, 23:09     Пирамидальная сортировка массива, счетчики #1
не могу понять куда счетчики:сравнения и обменов.помогите пожалуйста.
вот код сортировки:
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);
     }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.05.2014, 23:09     Пирамидальная сортировка массива, счетчики
Посмотрите здесь:

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

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Melg
416 / 152 / 62
Регистрация: 23.09.2013
Сообщений: 306
02.05.2014, 23:15     Пирамидальная сортировка массива, счетчики #2
Вы не могли бы конкретизировать свой вопрос примерно в следующем ключе: Я пытаюсь решить задачу "описание задачи". Для решения я хочу применить "описание решения". При попытке его применить я сталкиваюсь с проблемой "описание проблемы"? Тогда помочь Вам будет намного легче.
Gmails
5 / 5 / 2
Регистрация: 08.04.2014
Сообщений: 241
03.05.2014, 10:30  [ТС]     Пирамидальная сортировка массива, счетчики #3
задача:написать массив,упорядочить его с помощью пирамидальной сортировки.измерить количество обменов и сравнений при сортировке.выдать результат.пожалуйста помогите.

Добавлено через 8 часов 13 минут
помогите

Добавлено через 1 час 11 минут
up!
Yandex
Объявления
03.05.2014, 10:30     Пирамидальная сортировка массива, счетчики
Ответ Создать тему
Опции темы

Текущее время: 09:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru