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

@ozzy_b · Регистрация: 02.10.2012

Author24 — интернет-сервис помощи студентам

Парни, есть код етой сориторви, есть масив который надо посортировать. Но есть проблема, я не знаю что надо передать в функцию heapsort(int n), что такое n, ведь мне надо масив посортировать, почему не масив передаетья. Код "склеил" из лекции по алгоритмах сортировки.

C++

#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;
    }
}

@MaRKerNSK · 03.12.2012, 00:38

Вроде n это номер проверяемого элемента... или сортируемого, если вы содрали этот код с учебника то и объяснение его наверно можно найти там же

@ozzy_b · 03.12.2012, 00:43 **[ТС]**

MaRKerNSK, из лекции, где не особо все описано.

Добавлено через 57 секунд
MaRKerNSK, то как мне переписать мейн, чтоб правильно вызвать функцию сортировки?

@MaRKerNSK · 03.12.2012, 00:44

Да переписывать вроде ничего не надо) массив у тебя глобальный его отправлять никуда не надо ...

@ozzy_b · 03.12.2012, 00:46 **[ТС]**

MaRKerNSK, ну а номер проверяемого елемента откуда брать? а то ночь, бошка совсем не варит)

@MaRKerNSK · 03.12.2012, 00:47

Да у меня анологично 3,5 часа ночи, и бессоница, а мне на пары в 6 утра вставать... =(

@ozzy_b · 03.12.2012, 00:54 **[ТС]**

MaRKerNSK, )) то как номер передать, не подскажешь?

@MaRKerNSK · 03.12.2012, 00:56

Сообщение от ozzy_b

const int n = 10;

так ты n и передавай

C++

1	heapsort(n);

Ты и так её как константу обьявил)) так что вообще из функции её можеш выпилить))

@ozzy_b · 03.12.2012, 01:03 **[ТС]**

MaRKerNSK, чтото оно не сортирует))

C++

#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++

#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 секунд
точнее не сортирует((

@MaRKerNSK · 03.12.2012, 01:04

Блин ну не знаю... я алгоритм той сортировки не знаю... а почему тебе именно она нужна?? Если именно она то смотри алгоритм её=)

@ozzy_b · 03.12.2012, 01:05 **[ТС]**

MaRKerNSK, либо быстрая сортировка, либо ета.

@MaRKerNSK · 03.12.2012, 01:07

Ну по быстрой попробуй)) тут на форуме вроде не однократно обсуждалась)

@ozzy_b · 03.12.2012, 01:07 **[ТС]**

MaRKerNSK, есть код одногрупника, но я не очень понимаю как оно работает

C++

#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;
}

@ozzy_b · 03.12.2012, 01:08 **[ТС]**

во первых я не понимаю зачем там структура c int key и char info

@MaRKerNSK · 03.12.2012, 01:09

Оо блин не всё мозг не варит, извиняюсь но я отлучусь)) =)

@ozzy_b · 03.12.2012, 01:11 **[ТС]**

MaRKerNSK, ладно, спасибо хоть за ето))

@ozzy_b 2 / 2 / 1 Регистрация: 02.10.2012 Сообщений: 169
	03.12.2012, 01:08 [ТС]	14
	во первых я не понимаю зачем там структура c int key и char info 0

@MaRKerNSK 24 / 11 / 0 Регистрация: 26.11.2012 Сообщений: 110 Записей в блоге: 2
	03.12.2012, 01:09	15
	Оо блин не всё мозг не варит, извиняюсь но я отлучусь)) =) 1

@ozzy_b 2 / 2 / 1 Регистрация: 02.10.2012 Сообщений: 169
	03.12.2012, 01:11 [ТС]	16
	MaRKerNSK, ладно, спасибо хоть за ето)) 0

@MaRKerNSK 24 / 11 / 0 Регистрация: 26.11.2012 Сообщений: 110 Записей в блоге: 2
	03.12.2012, 00:38	2
	Вроде n это номер проверяемого элемента... или сортируемого, если вы содрали этот код с учебника то и объяснение его наверно можно найти там же 1

@ozzy_b 2 / 2 / 1 Регистрация: 02.10.2012 Сообщений: 169
	03.12.2012, 00:43 [ТС]	3
	MaRKerNSK, из лекции, где не особо все описано. Добавлено через 57 секунд MaRKerNSK, то как мне переписать мейн, чтоб правильно вызвать функцию сортировки? 0

@MaRKerNSK 24 / 11 / 0 Регистрация: 26.11.2012 Сообщений: 110 Записей в блоге: 2
	03.12.2012, 00:44	4
	Да переписывать вроде ничего не надо) массив у тебя глобальный его отправлять никуда не надо ... 1

@ozzy_b 2 / 2 / 1 Регистрация: 02.10.2012 Сообщений: 169
	03.12.2012, 00:46 [ТС]	5
	MaRKerNSK, ну а номер проверяемого елемента откуда брать? а то ночь, бошка совсем не варит) 0

@MaRKerNSK 24 / 11 / 0 Регистрация: 26.11.2012 Сообщений: 110 Записей в блоге: 2
	03.12.2012, 00:47	6
	Да у меня анологично 3,5 часа ночи, и бессоница, а мне на пары в 6 утра вставать... =( 1

@ozzy_b 2 / 2 / 1 Регистрация: 02.10.2012 Сообщений: 169
	03.12.2012, 00:54 [ТС]	7
	MaRKerNSK, )) то как номер передать, не подскажешь? 0

@MaRKerNSK 24 / 11 / 0 Регистрация: 26.11.2012 Сообщений: 110 Записей в блоге: 2
	03.12.2012, 01:04	10
	Блин ну не знаю... я алгоритм той сортировки не знаю... а почему тебе именно она нужна?? Если именно она то смотри алгоритм её=) 0

@ozzy_b 2 / 2 / 1 Регистрация: 02.10.2012 Сообщений: 169
	03.12.2012, 01:05 [ТС]	11
	MaRKerNSK, либо быстрая сортировка, либо ета. 0

@MaRKerNSK 24 / 11 / 0 Регистрация: 26.11.2012 Сообщений: 110 Записей в блоге: 2
	03.12.2012, 01:07	12
	Ну по быстрой попробуй)) тут на форуме вроде не однократно обсуждалась) 0