Алгоритм сортировки с помощью дерева выбора #542723

Всем доброго времени суток :-) Расбираюсь с различными (быстрыми) алгоритмами сортировки, и нашел интересный алгоритм "Алгоритм сортировки с помощью дерева выбора" (древесной сортровки), но реализации его нет, пытаюсь сам реализовать, хотя бы псевдокод. Алгоритм очень похож на пирамидальную сортировку (полное описание метода 'древесной сортровки' можно найти, например, у 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 Мои мысли по этому поводу: должна быть какая-то рекурсивная функция, которая проходит по уровням и сравнивает пары. Как запустить рекурсию я не знаю. Предлагаю вместе подумать над реализацией. Буду рад все присоединившимся ;-)

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

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

[Как запустить рекурсию я не знаю.] Рекурсия;

Тут искал?

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

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

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

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

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

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

УсЁ есть здесь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

серьезно???

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

Да, серьезно.

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

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

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

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

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

Вроде бы пишется рекурсивная процедура, которая обрабатывает оба поддерева, и больший элемент пишет вверх. то есть первый запуск Поднять, а в нем Процедура Поднять(i) Если i>maxIndex Тогда  Возврат; КонецЕсли; Поднять(2*i+1); Поднять(2*i+2); //И тут больший пишется в узел I. КонецПроцедуры Это типа первая или вторая часть алгоритма, котораязапускается несколько раз, пока изменений в дереве не будет, и есть типа даказательство что запускать придется не более чем Log N раз. Сейчас покурю, попробую точно вспомнить алгоритм, хотя нужен был он мне только один раз, и больше 20-ти лет назад, поэтому вспомнить будет тяжело.

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

я по пирамиде разобрался с кодом: 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);  } } тут получается просеивание эл-та сквозь пирамиду

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

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

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

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

см

да, в 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; //Определяем кол-во уровней        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;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;                /*arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;        arrA.push_back;*/        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 :-) действительно эта сортировка имеет иное название :-)

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

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

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

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

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

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

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

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

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

понятно ;-)

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

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