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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 5.00
p1ka4y777
 Аватар для p1ka4y777
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 155
06.11.2013, 20:35     Пирамидальная сортировка #1
Каким будет порядок элементов списка [3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1] после применения к нему этапа построения пирамиды? Поделитесь опытом, желанно парочку комментарий...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2013, 20:35     Пирамидальная сортировка
Посмотрите здесь:

пирамидальная сортировка C++
C++ Пирамидальная сортировка
C++ Пирамидальная сортировка
Пирамидальная сортировка C++
C++ Пирамидальная сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
reckless91
30 / 30 / 1
Регистрация: 01.11.2013
Сообщений: 63
06.11.2013, 21:10     Пирамидальная сортировка #2
Цитата Сообщение от p1ka4y777 Посмотреть сообщение
Каким будет порядок элементов списка [3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1] после применения к нему этапа построения пирамиды? Поделитесь опытом, желанно парочку комментарий...
С бинарными деревьями знаком?
p1ka4y777
 Аватар для p1ka4y777
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 155
06.11.2013, 21:37  [ТС]     Пирамидальная сортировка #3
Цитата Сообщение от reckless91 Посмотреть сообщение
С бинарными деревьями знаком?
да...
reckless91
30 / 30 / 1
Регистрация: 01.11.2013
Сообщений: 63
06.11.2013, 22:25     Пирамидальная сортировка #4
Цитата Сообщение от p1ka4y777 Посмотреть сообщение
да...
Для начала попробуй с лева направо добавлять элементы в дерево...
примерно так:
1 шаг -> 3 корень (нечего просеивать)
2 шаг -> 9 левый потомок
просеиваешь "9" вверх... 9>3 меняешь местами, теперь 9 -корень, 3 - левый
3 шаг -> 14 правый потомок
просеиваешь "14" вверх... 14>9 меняешь местами, теперь 14 -корень, 9 - правый , 3 - левый
ход мыслей понятен??? нарисуй конечное дерево или напиши в строку что получится... затем объясню дальше

Добавлено через 6 минут
или вот почитай http://iproc.ru/parallel-programming/lection-5/
там гифка тебе все лучше любого человека объяснит
p1ka4y777
 Аватар для p1ka4y777
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 155
06.11.2013, 23:34  [ТС]     Пирамидальная сортировка #5
Цитата Сообщение от reckless91 Посмотреть сообщение
Для начала попробуй с лева направо добавлять элементы в дерево...
примерно так:
1 шаг -> 3 корень (нечего просеивать)
2 шаг -> 9 левый потомок
просеиваешь "9" вверх... 9>3 меняешь местами, теперь 9 -корень, 3 - левый
3 шаг -> 14 правый потомок
просеиваешь "14" вверх... 14>9 меняешь местами, теперь 14 -корень, 9 - правый , 3 - левый
ход мыслей понятен??? нарисуй конечное дерево или напиши в строку что получится... затем объясню дальше
увидеть бы код...
reckless91
30 / 30 / 1
Регистрация: 01.11.2013
Сообщений: 63
06.11.2013, 23:44     Пирамидальная сортировка #6
Цитата Сообщение от p1ka4y777 Посмотреть сообщение
увидеть бы код...
Вот и я так думаю, пишите - посмотрим, подправим.
p1ka4y777
 Аватар для p1ka4y777
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 155
07.11.2013, 00:14  [ТС]     Пирамидальная сортировка #7
Цитата Сообщение от reckless91 Посмотреть сообщение
Вот и я так думаю, пишите - посмотрим, подправим.
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
void iswap(int &n1, int &n2)
{
    int temp = n1;
    n1 = n2;
    n2 = temp;
}
 
int main()
{
    int const n = 12;
    int a[n] = {3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1};
    for ( int i = 0; i < n; ++i ) 
   {
       a[i] = n - i; cout << a[i] << " "; 
   }
  //-----------сортировка------------// 
 
 
    int sh = 0; //смещение
    bool b = false;
    for(;;)
    {
        b = false;
        for ( int i = 0; i < n; i++ )
        {
            if( i * 2 + 2 + sh < n )
            {
                if( ( a[i + sh] > a[i * 2 + 1 + sh] ) || ( a[i + sh] > a[i * 2 + 2 + sh] ) )
                {
                    if ( a[i * 2 + 1 + sh] <  a[i * 2 + 2 + sh] ) 
                    {
                        iswap( a[i + sh], a[i * 2 + 1 + sh] );
                        b = true;
                    }
                    else if ( a[i * 2 + 2 + sh] < a[ i * 2 + 1 + sh]) 
                         {
                             iswap( a[ i + sh], a[i * 2 + 2 + sh]);
                             b = true;
                         }
                }
                //дополнительная проверка для последних двух элементов
               //с помощью этой проверки можно отсортировать пирамиду 
               //состоящую всего лишь из трех элементов
                    if( a[i*2 + 2 + sh] < a[i*2 + 1 + sh] ) 
                        {
                        iswap( a[i*2+1+sh], a[i * 2 +2+ sh] );
                        b = true;
                        }
            }
            else if( i * 2 + 1 + sh < n )
                 {
                     if( a[i + sh] > a[ i * 2 + 1 + sh] )
                     {
                         iswap( a[i + sh], a[i * 2 + 1 + sh] );
                         b = true;
                     }
                 }
        }
        if (!b) sh++; //смещение увеличивается, когда на текущем этапе 
                      //сортировать больше нечего
        if ( sh + 2 == n ) break; 
    }  //конец сортировки
 
 
    cout << endl << endl;
    for ( int i = 0; i < n; ++i ) cout << a[i] << " "; 
 
 
    _getch();
    return 0;
}
жду Вашей критики
reckless91
30 / 30 / 1
Регистрация: 01.11.2013
Сообщений: 63
07.11.2013, 00:50     Пирамидальная сортировка #8
Цитата Сообщение от p1ka4y777 Посмотреть сообщение
жду Вашей критики
Зачем вы используете const??? (int const n = 12
Зачем сначала инициализировать массив int a[n] = {3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1};
А затем его забивать совсем другим???
for ( int i = 0; i < n; ++i )
{
a[i] = n - i; cout << a[i] << " ";
}

Добавлено через 4 минуты
p1ka4y777, Можете не стараться ответить... да и критиковать я ничего не буду, какой смысл обсуждать комипаст http://easylab.net.ua/sortirovka/pir...aya-sortirovka
Рад за вас, что Вы нашли то, что искали... удачи

Добавлено через 9 минут
Цитата Сообщение от p1ka4y777 Посмотреть сообщение
Каким будет порядок элементов списка [3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1] после применения к нему этапа построения пирамиды?
P.S. Вот только это не то, что вам требуется исходя из задания
Правильный ответ: 20, 18, 15, 8, 17, ...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 02:57     Пирамидальная сортировка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
p1ka4y777
 Аватар для p1ka4y777
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 155
07.11.2013, 02:57  [ТС]     Пирамидальная сортировка #9
спасибо за Ваши отзывы)

Добавлено через 2 часа 4 минуты
Цитата Сообщение от reckless91 Посмотреть сообщение
P.S. Вот только это не то, что вам требуется исходя из задания
Правильный ответ: 20, 18, 15, 8, 17, ...
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
45
46
47
48
49
#include "stdafx.h"
#include <iostream>
using namespace std;
 
template<typename T>
void downHeap(T a[], long k, long n) 
{
    T new_elem;
    long number;
    new_elem = a[k];
 
    while(k <= n/2) 
{
        number = 2*k;
        if( number < n && a[number] < a[number+1] ) 
            number++;
        if( new_elem >= a[number] ) break; 
        // иначе 
        a[k] = a[number];
        k = number;
    }
    a[k] = new_elem;
}
 
template<typename T>
void heapSort(T a[], long size) 
{
    long i;
    T temp;
    for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
    for(i=size-1; i > 0; i--) 
    {
        temp=a[i]; a[i]=a[0]; a[0]=temp;
        downHeap(a, 0, i-1); 
         }
}
int main()
{
 
    int arr[12] = {3, 9, 14, 12, 2, 17, 15, 8, 6, 18, 20, 1};
    heapSort(arr, 12);
 
    cout<<"[ ";
    for(int i = 0; i < 12; ++i)
        cout<<arr[i]<<" ";
    cout<<"]"<<endl;
    system ("pause");
    return 0;
}
Yandex
Объявления
07.11.2013, 02:57     Пирамидальная сортировка
Ответ Создать тему
Опции темы

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