VPF::[C++]Пиpaмидальная сортировка. - Форум программистов

valfandra

Дата 31.3.2009, 06:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 31.3.2009

Репутация: нет
Всего: нет

Код


#include "iostream" 
#include "stdio.h" 
using namespace std; 

void sift( int *array, int L, int R ){ 
int i, j; 
int item; 
i = L; 
    j = 2*L; 
    item = array[L]; 
    if ( j < R && array[j] < array[j + 1] ) j++; 
      while ( j <= R && item < array[j] ){ 
          array[i] = array[j]; 
          i = j; 
          j = 2*j; 
          if ( j < R && array[j] < array[j + 1] ) j++; 
         } 
    array[i] = item; 
    } 

void heapsort( int *array, int size ){ 
int sort=0; 
int L, R; 
int item; 
    L = size/2; 
    R = size - 1; 
    while ( L > 0 ){  
          L--; 
          sift( array, L, R ); 
    } 
    while ( R > 0 ){  
          item = array[0]; 
          array[0] = array[R]; 
          array[R] = item; 
                    R--; 
          sift( array, L, R ); 
    } 
    cout<<"\nf: "<<sort; 
} 

void main(){ 
int i, size; 
int *array; 
   cout << "Kolivhestvo elementov: \n "; 
   cin >> size; 
array = new int[size]; 
cout << "Ishodnii massiv:  "<<endl; 
for ( i = 0; i < size; i ++ ){ 
array[i] = rand()%10000; 
cout << array[i] << " "; 
} 

heapsort( array, size ); 
cout << "\nSortirovannii: "; 
for ( i = 0; i < size; i ++ ){ 
cout << array[i] << " " ; 
}  
   cin.get(); 
}

как работает сортировка-я знаю. а каод не понимаю. помогите разобрать! а еще нужно подсчитать колво перестановок и сравнений

Это сообщение отредактировал(а) Rodman - 31.3.2009, 08:44

zim22

Дата 31.3.2009, 08:07 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(valfandra @ 31.3.2009, 06:11

)

. а каод не понимаю

мне что, опять комментарии в стихах писать...

#include "iostream" - здесь мы подключаем заголовочный файл для юзанья классов cout, cin
... может вам MSDN почитать?

--------------------

C++ FAQ Lite

valfandra

Дата 31.3.2009, 08:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 31.3.2009

Репутация: нет
Всего: нет

void sift( int *array, int L, int R ){ // подключаем функцию. как я поняла для построения дерева?
i = L;
    j = 2*L;  // а это все последовательность и последовательность разбитая надва?
item = array[L]; // заносим в item л-тый элемент массива. те хвост?

if ( j < R && array[j] < array[j + 1] ) j++; // если индекс нашей последовательности меньше р? р это хвост? вот тут уже не понимаю

while ( j <= R && item < array[j] ){
          array[i] = array[j];
          i = j;
          j = 2*j;
          if ( j < R && array[j] < array[j + 1] ) j++;
      }
    array[i] = item;
    }
// пока условия не понятны. и дальнейшие действия тоже не понятно. i=j j=2*j - это наверно родитель и потомки?

void heapsort( int *array, int size ){ // это сама сортировка уже
L = size/2;
    R = size - 1; // середина последовательности и крайний элемент справа?

while ( L > 0 ){  // пока середина больше нуля. а когда она будет меньше?
L--;
          sift( array, L, R );// Л уменьшаем и втыкаем фцнцию для построения дерева? те мы где-то уже вершину с хвостом поменяли, хвост записали в item, а принцип дерева нарушен? поэтомутут вставляем функию для дерева?

while ( R > 0 ){
          item = array[0];
          array[0] = array[R];
          array[R] = item;
          sort++;
          R--;
          sift( array, L, R ); // а это для чего?

zim22

Дата 31.3.2009, 08:37 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

valfandra, я могу вам посоветовать реализовать сортировку самостоятельно. не такая уж она и сложная. заодно разберётесь.

--------------------

C++ FAQ Lite

valfandra

Дата 31.3.2009, 08:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 31.3.2009

Репутация: нет
Всего: нет

zim22, а не можете по этому коду помочь? пожалуйста smile

valfandra

Дата 31.3.2009, 12:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 31.3.2009

Репутация: нет
Всего: нет

помогите чсло срванений и перестановок посчиатьь

zim22

Дата 31.3.2009, 15:04 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(valfandra @ 31.3.2009, 12:38

)

помогите чсло срванений и перестановок посчиатьь

создайте переменные-счётчики. при каждой перестановке или сравнении инкрементируйте соотв.счётчик. в конце работы функции счётчики будут содержать нужные вам значения.

--------------------

C++ FAQ Lite

Dmi3ev

Дата 31.3.2009, 21:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 5
Всего: 41

http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%...%B2%D0%BA%D0%B0
тут уже все реализовано

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »