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

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

Войти
Регистрация
Восстановить пароль
 
 
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
#1

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

03.12.2012, 00:33. Просмотров 482. Ответов 15
Метки нет (Все метки)

Парни, есть код етой сориторви, есть масив который надо посортировать. Но есть проблема, я не знаю что надо передать в функцию heapsort(int n), что такое n, ведь мне надо масив посортировать, почему не масив передаетья. Код "склеил" из лекции по алгоритмах сортировки.
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
#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;
 
struct INF
{
    int key;
    char info;
};
const int n = 10;
INF mas[n];
void heapsort (int);
void pushdown (int, int ) ;
void SWAP(int  ,int );
 
int main()
{
    srand(time(0));
    cout<<"MAS"<<endl<<endl;
    for(int i = 0;i < n;i++)
    {
        mas[i].key = rand()%20;
        cout<<mas[i].key<<" ";
    }
    cout<<endl<<endl;
    cout<<"Qsort";
    heapsort();
    getch();
    return 0;
}
void heapsort (int n) 
{
    for (int i=1; i<=(n/2); i++)
       pushdown (i, n);
 
    for (int i = n; i > 1; i--) 
    {         
        swap (mas[1], mas[0]);
        pushdown (1, i-1);
    }
}
void pushdown (int first, int last) 
{
    int j;
    int r = first;                                        
    while (r<=(last/2)) 
    {
        if ((2*r==last)||(mas[r*2].key<mas[2*r+1].key))
            j = 2*r;
        else
            j=2*r+1;
        if (mas[r].key>mas[j].key) 
        {
            swap(mas[r],mas[j]);
            r = j;
        }
        else
        break;
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2012, 00:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пирамидальная соритровка (C++):

Соритровка слиянием - C++
Всем доброго времени суток! В универе задали задачку на сортировку списка слиянием, в теории я всё понял, только не понял как это...

Алфавитная соритровка структур из файла - C++
Всем доброе утро. struct zapchasti { char firma; char tovar; int kol; int cena; int garantia;

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

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

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

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

15
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 00:38 #2
Вроде n это номер проверяемого элемента... или сортируемого, если вы содрали этот код с учебника то и объяснение его наверно можно найти там же
1
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 00:43  [ТС] #3
MaRKerNSK, из лекции, где не особо все описано.

Добавлено через 57 секунд
MaRKerNSK, то как мне переписать мейн, чтоб правильно вызвать функцию сортировки?
0
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 00:44 #4
Да переписывать вроде ничего не надо) массив у тебя глобальный его отправлять никуда не надо ...
1
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 00:46  [ТС] #5
MaRKerNSK, ну а номер проверяемого елемента откуда брать? а то ночь, бошка совсем не варит)
0
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 00:47 #6
Да у меня анологично 3,5 часа ночи, и бессоница, а мне на пары в 6 утра вставать... =(
1
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 00:54  [ТС] #7
MaRKerNSK, )) то как номер передать, не подскажешь?
0
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 00:56 #8
Цитата Сообщение от ozzy_b Посмотреть сообщение
const int n = 10;
так ты n и передавай
C++
1
heapsort(n);
Ты и так её как константу обьявил)) так что вообще из функции её можеш выпилить))
1
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 01:03  [ТС] #9
MaRKerNSK, чтото оно не сортирует))
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
#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;
 
struct INF
{
    int key;
    char info;
};
const int n = 10;
INF mas[n];
void heapsort (int);
void pushdown (int, int ) ;
void SWAP(int  ,int );
 
int main()
{
    srand(time(0));
    cout<<"MAS"<<endl<<endl;
    for(int i = 0;i < n;i++)
    {
        mas[i].key = rand()%20;
        cout<<mas[i].key<<" ";
    }
    cout<<endl<<endl;
    cout<<"Qsort";
     for(int i = 0;i < n;i++)
    {
        mas[i].key = rand()%20;
        cout<<mas[i].key<<" ";
    }
    heapsort(n);
    getch();
    return 0;
}
void heapsort (int n) 
{
    for (int i=1; i<=(n/2); i++)
       pushdown (i, n);
 
    for (int i = n; i > 1; i--) 
    {         
        swap (mas[1], mas[0]);
        pushdown (1, i-1);
    }
}
void pushdown (int first, int last) 
{
    int j;
    int r = first;                                        
    while (r<=(last/2)) 
    {
        if ((2*r==last)||(mas[r*2].key<mas[2*r+1].key))
            j = 2*r;
        else
            j=2*r+1;
        if (mas[r].key>mas[j].key) 
        {
            swap(mas[r],mas[j]);
            r = j;
        }
        else
        break;
    }
}
Добавлено через 2 минуты
ой, ступил, сечас переправлю

Добавлено через 41 секунду
всеравно не сортирует как надо
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;
 
struct INF
{
    int key;
    char info;
};
const int n = 10;
INF mas[n];
void heapsort (int);
void pushdown (int, int );
void SWAP(int  ,int );
 
int main()
{
    srand(time(0));
    cout<<"MAS"<<endl<<endl;
    for(int i = 0;i < n;i++)
    {
        mas[i].key = rand()%20;
        cout<<mas[i].key<<" ";
    }
    cout<<endl<<endl;
    cout<<"Qsort";
     for(int i = 0;i < n;i++)
    {
        cout<<mas[i].key<<" ";
    }
    heapsort(n);
    getch();
    return 0;
}
void heapsort (int n) 
{
    for (int i=1; i<=(n/2); i++)
       pushdown (i, n);
 
    for (int i = n; i > 1; i--) 
    {         
        swap (mas[1], mas[0]);
        pushdown (1, i-1);
    }
}
void pushdown (int first, int last) 
{
    int j;
    int r = first;                                        
    while (r<=(last/2)) 
    {
        if ((2*r==last)||(mas[r*2].key<mas[2*r+1].key))
            j = 2*r;
        else
            j=2*r+1;
        if (mas[r].key>mas[j].key) 
        {
            swap(mas[r],mas[j]);
            r = j;
        }
        else
        break;
    }
}


Добавлено через 25 секунд
точнее не сортирует((
0
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 01:04 #10
Блин ну не знаю... я алгоритм той сортировки не знаю... а почему тебе именно она нужна?? Если именно она то смотри алгоритм её=)
0
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 01:05  [ТС] #11
MaRKerNSK, либо быстрая сортировка, либо ета.
0
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 01:07 #12
Ну по быстрой попробуй)) тут на форуме вроде не однократно обсуждалась)
0
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 01:07  [ТС] #13
MaRKerNSK, есть код одногрупника, но я не очень понимаю как оно работает
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
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;
 
struct INF
{
    int key;
    char info;
};
const int n = 10;
INF mas[n];
int partition(int ,int ,int );
int find_pivot(int ,int );
void SWAP(int ,int );
 
 
void quick_sort(int i,int j)
{
    int pivot;
    int pivotindex;
    int k;
    pivotindex = find_pivot(i,j);
    if(pivotindex != -1)
    {
        pivot = mas[pivotindex].key;
        cout<<endl<<endl;
        k = partition(i,j,pivot);
        for(int i = 0;i < n;i++)
        {
            cout<<mas[i].key<<" ";
        }
        quick_sort(i,k-1);
        quick_sort(k,j);
    }
 
}
int main()
{
    srand(time(0));
    cout<<"MAS"<<endl<<endl;
    for(int i = 0;i < n;i++)
    {
        mas[i].key = rand()%20;
        cout<<mas[i].key<<" ";
    }
    cout<<endl<<endl;
    cout<<"Qsort";
    quick_sort(0,n-1);
    getch();
    return 0;
}
int find_pivot(int i,int j)
{
    int firstkey;
    firstkey = mas[i].key;
    for(int k=i+1;k <= j;k++)
    {
        if(mas[k].key > firstkey)
            return k;
        else
            if(mas[k].key < firstkey)
                return i;
    }
    return -1;
}
int partition(int i,int j,int pivot)
{
    int l,r;
    l = i;
    r = j;
    do
    {
        SWAP(l,r);
        while(mas[l].key < pivot)
            l++;
        while(mas[r].key >= pivot)
            r--;
    }
    while(l <= r);
    return l;
}
void SWAP(int a,int b)
{
    INF temp = mas[a];
     mas[a] = mas[b];
     mas[b] = temp;
}
0
ozzy_b
2 / 2 / 0
Регистрация: 02.10.2012
Сообщений: 169
03.12.2012, 01:08  [ТС] #14
во первых я не понимаю зачем там структура c int key и char info
0
MaRKerNSK
24 / 11 / 1
Регистрация: 26.11.2012
Сообщений: 110
Записей в блоге: 2
03.12.2012, 01:09 #15
Оо блин не всё мозг не варит, извиняюсь но я отлучусь)) =)
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2012, 01:09
Привет! Вот еще темы с ответами:

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

Пирамидальная сортировка - C++
Здравствуйте, написал пирамидальную сортировку с костылями, которая вроде и работает, но если сдавать, то 10 тестов из 30 проходит, вот...

Пирамидальная сортировка - C++
int HeapSort (int *a, int n) { int left = n/2+1, right=n-1, x; while (left&gt;1) sift (a, --left, right); while (right&gt;1) {...

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
03.12.2012, 01:09
Ответ Создать тему
Опции темы

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