Всем доброго времени суток :-)
Расбираюсь с различными (быстрыми) алгоритмами сортировки, и нашел интересный алгоритм "Алгоритм сортировки с помощью дерева выбора" (древесной сортровки), но реализации его нет, пытаюсь сам реализовать, хотя бы псевдокод. Алгоритм очень похож на пирамидальную сортировку (полное описание метода 'древесной сортровки' можно найти, например, у H. Вирта в книге 'Алгоритмы + Структуры Данных = Программы'.), но строится не представление данных в виде дерева, а 'дерево выбора' (т.е. данные должны храниться в одном массиве).
В качестве примера: есть массив (3,1,3,4,5,1,7,4), Сортировка начинается с построения дерева выбора: просматриваются пары элементов (i+1),(i+2) и минимальный становится родителем пары, затем просматриваются пары родителей и т.д. пока не будет найден минимальный элемент. Структура поддерева такая i - родитель, 2i+1 и 2i+2 сыновья.
В итоге дерево будет иметь вид:

             1
        1              1
  1        3       1       4
3   1    3   4   5   1   7   4

Мои мысли по этому поводу: должна быть какая-то рекурсивная функция, которая проходит по уровням и сравнивает пары. Как запустить рекурсию я не знаю.
Предлагаю вместе подумать над реализацией. Буду рад все присоединившимся ;-)

зачем нам думать?

"Как запустить рекурсию я не знаю".
Мда... Как алгоритмы с деревьми строить - это мы запросто. А как сделать рекурсию - все, приплыли...

(0)[Как запустить рекурсию я не знаю.]

Рекурсия();

(0) Тут искал?
http://algolist.manual.ru/

(1) можешь не думать, разрешаю :-)

(2,3) а что-нибудь по сути сказать есть или только флуд??? :-)))

(4) спасибо. смотрел, там описана пирамидальная сортировка.
с ней более-менее все понятно - смысл в том что максимальный (минимальный) элемент как бы всплывает на поверхность (т.е. берется элемент и двигается, пока не станет максимумом, либо меньше максимального), а тут элементы сравниваются парами

если есть сыновья, то где дочери ?

(7) ладно-ладно, уговорил чертяка :-) можешь быть дочерью :-)))

реккурсия? в 1С? ну-ну...

Чтобы запустить рекурсию, надо (вы не поверите) - запустить рекурсию...

УсЁ есть здесь wiki:Tree_sort

(10) да не в этом дело даже... автор же хочет ускориться... только не понимает, что язык 1С не предназнячен для построения простых алгоритмов. Пусть хотя бы число Пи посчитает - на определенном уровне вложенности рекурсии платформа упадет просто. Какое там ускорение, когда среда падает от таких режимов?

(9) да почему в 1с?! секция "Математика и алгоритмы"
просто хотя бы написать псевдокод, как это должно работать.
вот у меня есть мысли что нужно проходить по уровням, а затем по элементам уровней, вот только не могу сообразить как допустим выходить из рекурсии - когда индекс на уровне за пределами массива или заранее считать кол-во элементов на уровне, но это уже не секурсия

(10)ну а по сути что-нибудь есть?!

(11) это немного не то
в задаче, которую я описал строится некое дерево минимумов (максимумов)

(12) да я еще раз говорю - я не слова не сказал про 1с
для начала хотя бы написать псевдокод.

бинарное дерево - уже отсортированное

(15) "строится некое дерево минимумов (максимумов)" И что? Чем это отличается от построения бинарного дерева? Что находится в узлах оного по вашему мнению?

(17) в усовии задачи нет слова "бинарное дерево".
ради интереса открой Вирта 'Алгоритмы + Структуры Данных = Программы'. Там описана пирамидальная сортировка достаточно подробно с псевдокодом, а про сортировку деревом выбора "слегка" написано. Вот я и хочу разобраться как это делается. Своими силами не получается, вот и вынес задачу на суд общественности

(18) вот допустим описание: http://citforum.ru/programming/theory/sorting/sorting1.shtml#2_5

вот как его построить???
и это не бинарное дерево, т.к. оно не сотрированное

(19) ты дурак или как ?

"
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое двоичное дерево, у которого выполнены условия:

  1. Каждый лист имеет глубину либо d, либо d ? 1, d — максимальная глубина дерева.
  2. Значение в любой вершине больше, чем значения её потомков.
"

wiki:Heapsort

(21)уважаемый!!! на личности не надо переходить!!!

(22) так книжки читай тогда внимательно

(5) По сути? Ну сам напросился...
"- Вы стоите на самой низшей ступени развития! - перекричал Филипп Филиппович, - вы еще только формирующееся, слабое в умственном отношении существо, все ваши поступки чисто звериные, и вы, в присутствии двух людей с университетским образованием, позволяете себе с развязностью совершенно невыносимой, подавать какие-то советы космического масштаба и космической же глупости о том, как все поделить, и вы в то же время наглотались зубного порошку!.."
Это вот про тебя.

Бог ты мой, академические изыскания на мисте... во делать нефиг...

(23) открой Вирт Н. Алгоритмы и структуры данных страница 108, там описана сортировка с помощью дерева, а дальше про пирамидальную. Еще раз акцентирую, что с пирамидальной более-менее все понятно, а с деревом выбора не понятно.
я по поводу пирамидальной с тобой не спорю, так оно и есть.
я спрашиваю у сообщества как быть с построением дерева выбора.

(24) совершенно не понятно к чему это :-)
ты пьяный что ли?
а по теме вопроса что-нибудь можешь сказать? :-)

(25) нет, не академические. просто стало интересно...

Правильное название - корпоративная сортировка.
Во всяком случае нам в далеком 89-ом давали такое название.

(29)серьезно???

(29) подробнее можете рассказать?

(30) Да, серьезно.

(32)спасибо. попробую завтра поискать в лит-ре.
по крайней мере у Вирта и Сэджвика такого названия не встречал. Да и именно про описанный метод в (0) у них мало информации :-(

Все больше и больше убеждаюсь в практической ценности всяких сортировок всякими методами.

Была книга у меня тогда, в которой описывались битовые методы защиты и избыточного кодирования данных (типа кода Хэмминга) и там давалось тоже название (корпоративная) что и давали нам на сборах на союз. Помню что книга - перевод с Японского :)
Сам алгоритм плохо помню, ибо он на практике не применяется (при малых размерах массива быстрее Шелл, при больших - всякие квиксорты, слияние отрезков и т.д.) Но тогда тоже помню что с пониманием корпоративной сортировки у меня возникли некоторые проблемы. (нужно было выучить за вечер, а на вечер еще и кучу задач ежедневно давали) Но вроде выучил, и на следующий день написал.

Сейчас единственно что помню - как массив представляется в виде бинарного дерева (если нумерация с нуля, то у каждого узла I - дочерние - 2i+1 и 2i+2), и что сначала элементы поднимают, потом опускают (или наоборот), то есть алгоритм состоит из двух частей.

(35)благодарю за инфу.
попробовал погуглить - информации нет.
у меня ситуация проще :-) сдавать ничего не надо.
сегодня наткнулся на описание этого алгоритма и стало интересно. чем-то он меня зацепил, хочу найти решение :-)

Вроде бы пишется рекурсивная процедура,
которая обрабатывает оба поддерева, и больший элемент пишет вверх.
то есть первый запуск
Поднять(0), а в нем

Процедура Поднять(i)
Если i>maxIndex Тогда
 Возврат;
КонецЕсли;
Поднять(2*i+1);
Поднять(2*i+2);
//И тут больший пишется в узел I.
КонецПроцедуры

Это типа первая или вторая часть алгоритма, котораязапускается несколько раз, пока изменений в дереве не будет, и есть типа даказательство что запускать придется не более чем Log N раз.

Сейчас покурю, попробую точно вспомнить алгоритм, хотя нужен был он мне только один раз, и больше 20-ти лет назад, поэтому вспомнить будет тяжело.

(36) она везде написана что у вирта, что у сэджвика на уровне: "С помощью n/2 сравнений можно определить наименьший элемент из каждой пары, при помощи следующих n/4 — наименьший из каждой пары таких наименьших ключей и т.д. При этом за n-1 сравнений мы можем построить дерево выбора..."
И ни одного толкового объяснения как же это дерево строится — не говоря уже о коде.
просто еще у меня мысль родилась - вот пирамидальна она на четном и нечетном кол-ве элементов, а здесь получается на парах должна быть. и как быть в случае с отсутсвием у одного эл-та пары

(38) я по пирамиде разобрался с кодом:
template<class T>
void downHeap(T a[], long k, long n) {
 //  процедура просеивания следующего элемента
 //  До процедуры: a[k+1]...a[n]  - пирамида
 //  После:  a[k]...a[n]  - пирамида
 T new_elem;
 long child;
 new_elem = a[k];

 while(k <= n/2) {          // пока у a[k] есть дети
   child = 2*k;
   //  выбираем большего сына
   if( child < n && a[child] < a[child+1] )
   child++;
   if( new_elem >= a[child] ) break;
   // иначе
   a[k] = a[child];    // переносим сына наверх
   k = child;
 }
 a[k] = new_elem;
}

template<class T>
void heapSort(T a[], long size) {
 long i;
 T temp;

 // строим пирамиду
 for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
 
 // теперь a[0]...a[size-1] пирамида

 for(i=size-1; i > 0; i--) {
   // меняем первый с последним
   temp=a[i]; a[i]=a[0]; a[0]=temp;

   // восстанавливаем пирамидальность a[0]...a[i-1]
   downHeap(a, 0, i-1);
 }
}

тут получается просеивание эл-та сквозь пирамиду

(39) Нет пары и нет. какие проблемы? :)
У тебя получается либо только вершина, либо только вершина и левый дочерний узел.

а древесная получается, что есть входной массив размерностью N, итоговое дерево будет размером 2*N-1. Нижний уровень нам тоже известен. это есть ничто иное как входной массив.
осталось выстроить n-1 элемент

(41) да, согласен. или можно отсутствующий в паре элемент заменять на бесконечность

(42) дальше, как мне кажется, нужно идти по уровням, которых у нас N/2, а затем по элементам уровня, сравнивая пары. вот здесь у меня и затык полный. как должна сработать рекурсия и как из неё выходить, я не понима...

(44) см (38)

(45) да, в 40 подобное реализовано.

Реализовал на с++, публикую для тех кому интересно.


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

       //Установка размера выходного массива
       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<N; i++){
               if (arrA[i]>MaxA) MaxA = arrA[i];
       }

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

void TreeSort(void){

       int k = 0;
       int i, minA;
       //int j = 0;

       while (k < N){
               i = 1;
               if (arrB[i] == infinity) break;

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

               //Спуск по дереву
               while (i < 2*N){
                       if (2*i+1 > 2*N-1){
                               arrA[k] = minA;
                               arrB[i] = infinity;
                               break;
                       }

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

               //Подъем по дереву
               while(i > 1){
                       //Определить четность i-го элемента
                       if (i%2 == 1){//Нечетный элемент
                               if (arrB[i] > arrB[i-1]) arrB[(i-1)/2] = arrB[i-1];
                               else arrB[(i-1)/2] = arrB[i];
                       }
                       else{//Четный элемент
                               if (arrB[i] > arrB[i+1]) arrB[i/2] = arrB[i+1];
                               else arrB[i/2] = arrB[i];
                       };

                       //Обнуляем текущий элемент
                       //arrB[i] = infinity;

                       i=i/2;
               }

               k+=1;
               //if (k > (N-1)) break;
       }

}
//---------------------------------------------------------------------------


void main(void)
{

       //Заполнение исходного вектора
       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(3);        

       /*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);*/

       N = arrA.size();

       for (int i=0; i<N-1; i++){
               cout << arrA[i] << " | ";
       }
       cout << endl;
       cout << endl;


       CreateTree();

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

       cout << "| ";
       for (int i=0; i<2*N-1; i++){
               cout << arrB[i] << " | ";
       }
       cout << endl;

       cout << "| ";
       for (int i=0; i<2*N-1; 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;
       }*/


       TreeSort();


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

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

Возможно есть более изящная реализация. Моя не претендует на оптимальность и совершенство, я просто реализовал алгоритм.
Еще один момент хочу отметить: алгоритм применим в основном для массивов размерность которых кратна степени 2, т.е. 2^1=2, 2^2=4, 2^3=8, 2^4=16 и т.д.

особый респект NS :-) действительно эта сортировка имеет иное название :-)

(49) у кнута посмотри в 3 томе - мот там тоже описывается, я не помню уже.

(49) Нашел термин "корпоративная"?

Вспомнил - еще всплывало иерахия, иерархиями или иерархичная. Слово корпоративная - могло возникнуть из-за нечеткого перевода с японского.

(51) да, сходил в библиотеку :-) там ксерокопия с какой-то старой книги была...вот там и нашел такой термин.

(50) спасибо ;-) но не нашел у кнута, может мне не по глазам :-)

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

все думают, что производство велосипедов бессмысленная трата времени.
На самом деле производство велосипеда - экзамен на профпригодность.

(56) и как думаешь, я профпригоден? или безнадежен??? :-)))

(57) нет времени разбираться.

(58) понятно ;-)

(57) Вообще - это сложная задача. Насколько я помню единственное что очень тяжело мне (да и остальным участникам сборов) далось на сборах на союз.

то есть вообще давалось не с практической целью, а чтоб голову как следует поломать.

(60) согласен, не тривиальная задачка, не имеющая практического применения...