Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 07.04.2011, 16:24
queit

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
Вот что Вирт животворящий пишет:
это уже не Вирт, а Уилльямсон придумал нормальное (с точки зрения оптимальности) дерево : -)
а у Вирта своё дерево. я именно его пытаюсь реализовать.
ща сортировку сделаю...посмотрю что получится
  #12  
Старый 07.04.2011, 19:05
гщсть

 
Сообщений: n/a

так я так и нифига не понял что вам нужно

heap sort aka пирамидальная сортировка? или нет?
  #13  
Старый 08.04.2011, 07:17
queit

 
Сообщений: n/a

Сообщение от гщсть Посмотреть сообщение
так я так и нифига не понял что вам нужно

heap sort aka пирамидальная сортировка? или нет?
Именно, алгоритм сортировки деревом выбора.
Вирт Н. "Алгоритмы и структуры данных" страница 108

но у же не так актуально, сегодня доделаю саму сортировку...если по вермени успею.
  #14  
Старый 08.04.2011, 08:19
гостъ

 
Сообщений: n/a

http://en.wikibooks.org/wiki/Algorit...rting/Heapsort
  #15  
Старый 08.04.2011, 08:26
queit

 
Сообщений: n/a

Сообщение от гостъ Посмотреть сообщение
http://en.wikibooks.org/wiki/Algorit...rting/Heapsort
ну не совсем то, конечно.
в русской это нечто подобное: http://ru.wikipedia.org/wiki/Heapsort

+ реализация на с++ похожая и впечатляет :-) что находится в #include <algorithm> остается загадкой
  #16  
Старый 08.04.2011, 09:18
гостъ

 
Сообщений: n/a

Сообщение от queit Посмотреть сообщение
+ реализация на с++ похожая и впечатляет :-) что находится в #include <algorithm> остается загадкой

ровно то что полагается по стандарту

Цитата:
ну не совсем то, конечно.
шо значит не совсем то? я спрашивал - heapsort, вы сказали да
  #17  
Старый 08.04.2011, 13:50
queit

 
Сообщений: n/a

Сообщение от гостъ Посмотреть сообщение
ровно то что полагается по стандарту


шо значит не совсем то? я спрашивал - heapsort, вы сказали да
Вы открывали Вирта Н. "Алгоритмы и структуры данных" страница 108???
вот там алгоритм, ровно до того момента как его усовершенствовал Уилльямсон. Это не Heapsort! Различия в построении дерева.
  #18  
Старый 08.04.2011, 15:15
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

гостъ
Не заморачивайтесь.
subj в чистом виде есть умозрительная бесполезная хрень с двойным расходом памяти.

Под идею была придумана (или подогнана) структура данных heap, и получился heapsort.
  #19  
Старый 08.04.2011, 15:42
гостъ

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
гостъ
нет, queit

Цитата:
Не заморачивайтесь.
согласен

Цитата:
с двойным расходом памяти.
тройным даже

Цитата:
subj в чистом виде есть умозрительная бесполезная хрень
ну, есть одно полезное свойство в отличие от heapsort - она может сортировать стабильно.
  #20  
Старый 11.04.2011, 08:03
queit

 
Сообщений: n/a

вот что у меня получилось:

#include <iostream>
#include <conio>
#include <stdlib.h>
#include <stdio.h>
#include <math>
#include <string.h>
#include <stdlib.h>
#include <vector>

using namespace std;
//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------

int N;
vector <int> arrB, arrC, arrA;
int infinity;
//---------------------------------------------------------------------------

#pragma argsused

void CreateTree(void)
{
int i,j,L,H,minA,v;

//Установка размера выходного массива
N = arrA.size();
arrB.resize(N);

//Заполнение вспомагательного вектора
arrC = arrA;

L = log(N)/log(2); //Определяем кол-во уровней
for (j = 0; j < L; j++){
//На последнем этапе итерации просто устанавливаем в корень
//минимальный элемент на прошлом этапе
if (j==(L-1)){
arrB[1] = min(arrB[2],arrB[3]);
return;
}
//Определение размера вспомогательного массива
H = arrC.size();
i = 1;
while(i < H){
//Итератор для результирующего массива
//int v = 0;
if (i==1){
v = pow(2, L-j)/2;
}
else v+=1;

//Определение минимального элемента из пары i и i+1
if (arrC[i-1] < arrC[i]){
minA = arrC[i-1];
}
else{
minA = arrC[i];
}

//Установка мин.значения в результирующий массив
arrB[v] = minA;
//Добавим во вспомогательный массив мин. элемент
arrC.push_back(minA);

i=i+2;
}
//Изменаем размер вспомагательного массива
vector<int>::iterator p = arrC.begin();
arrC.erase(p - 1, p - 1 + H);
}
}
//---------------------------------------------------------------------------

void DefineInfinity(void){
int MaxA;
MaxA = arrA[0];
for (int i=0; i<arrA.size(); i++){
if (arrA[i]>MaxA) MaxA = arrA[i];
}

infinity = MaxA + 1;
}
//---------------------------------------------------------------------------

bool TreeSort(int i, int k){
int minA;

if (arrB[i] < infinity){
//Текущий элемент является минимальным
minA = arrB[i];
//Обнуляем текущий элемент
arrB[i] = infinity;

while (i < 2*N - 1){
if (2*i+1 > 2*N-1){
arrA[k] = minA;
arrB[i] = infinity;
return true;
}

if (arrB[2*i] == minA){
arrB[i] = infinity;
i = 2*i;
}
else if (arrB[2*i+1] == minA){
arrB[i] = infinity;
i = 2*i + 1;
}
}
}
else return false;
}
//---------------------------------------------------------------------------

void main(void)
{

//Заполнение исходного вектора
arrA.push_back(3);
arrA.push_back(1);
arrA.push_back(3);
arrA.push_back(4);
arrA.push_back(5);
arrA.push_back(1);
arrA.push_back(7);
arrA.push_back(4);

/*arrA.push_back(1);
arrA.push_back(2);
arrA.push_back(3);
arrA.push_back(4);
arrA.push_back(5);
arrA.push_back(6);
arrA.push_back(7);
arrA.push_back(8);
arrA.push_back(9);
arrA.push_back(10);
arrA.push_back(11);
arrA.push_back(12);
arrA.push_back(13);
arrA.push_back(14);
arrA.push_back(15);
arrA.push_back(16);*/

for (int i=0; i<arrA.size(); i++){
cout << arrA[i] << " | ";
}
cout << endl;
cout << endl;


CreateTree();

//Дописываем в конец результирующего массива исходный (нижний уровень в дереве)
for (int i=0; i<arrA.size(); i++) arrB.push_back(arrA[i]);

cout << "| ";
for (int i=0; i<arrB.size(); i++){
cout << arrB[i] << " | ";
}
cout << endl;

cout << "| ";
for (int i=0; i<arrB.size(); i++){
if (i>9) cout << i << "| ";
else cout << i << " | ";
}
cout << endl;

cout << endl;
DefineInfinity();
cout << "Infinity = " << infinity << endl;
cout << endl;
cout << endl;

int k = 0;
for (int i = 1; i < 2*N - 1; i++){
if (TreeSort(i,k)) k+=1;
}


for (int i=0; i<arrA.size(); i++){
cout << arrA[i] << " | ";
}
cout << endl;

getch();
}
//---------------------------------------------------------------------------


дерево вроде бы строится правильно. С самой сортировкой я вообще не знаю как быть. Проблема в том что, мне не понятно как определять индекс элемента в выходном массиве...:-(
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм наилучшего взаимного выбора Detech Математические алгоритмы (другое) 6 17.11.2010 04:52
Вопрос по правильности выбора обучения Serg555 Искусственный интеллект, нейронные сети 1 16.03.2010 20:03
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49
Алгоритм, который определяет, является ли граф деревом trans-tech Сортировка и поиск 1 26.11.2008 15:55
Метод квадратичного выбора ToR Сортировка и поиск 12 05.11.2008 23:02