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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248
#1

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

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

Пирамидальная сортировка массива - C++
Помогите, пожалуйста, написать программу и блок-схему к задаче Получить упорядоченный массив чисел в порядке возрастания его элементов с...

Пирамидальная сортировка, добавить ввод размера массива пользователем - C++
Есть программа для пирамидальной сортировки. Как сделать так чтобы пользователь сам вводил размерность массива? #include &lt;stdio.h&gt; ...

Сортировка. Счетчики - C++
Всем привет, достаточно долго сижу на этом сайте, вот в первые решил попросить помощи, надеюсь на вас! Вообщем задание было следующее:...

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....

Пирамидальная сортировка - C++
Здравствуйте! Хотела попросить помощи. Мне нужно отсортировать дерево пирамидальной сортировкой. Создание дерева у меня есть, но сортировка...

Пирамидальная сортировка - C++
Добрый Вечер! Нужно сделать Пирамидальную сортировку. Немного получилось, но программа работает так как хотелось бы. Не сортирует...

Пирамидальная сортировка - C++
Есть программа для пирамидальной сортировки но сортирует в другую сторону от меньшего к большему, а нужно наоборот, как исправить ...

Пирамидальная сортировка по убыванию - C++
Всем привет. Требуется реализовать пирамидальную сортировку по убыванию. Как делается сортировка по возрастанию мне известно. Как это можно...

сортировка пирамидальная(с++)плз ответ - C++
сортировка пирамидальная(с++)плз ответ!!! мне задавали вопросы что выполняет???( for(i=10; i&gt;=1; i--) //-? { ...


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

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

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

Добавлено через 1 час 11 минут
up!
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru