Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=689588 Wed, 20 Apr 2005 20:15:02 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=689588 сравнений(чтобы понимать, куда идтить, влево или вправо). После того, как мы заменяем один из элементов массива(наименьший из сущ.) на "дыру", мы должны скорректировать дерево и подняться наверх. для этго ведь тоже надо log n сравнений! Всего получаем 2log n*n Почему же везде пишут, что их log2*n? Объясните мне, пожалуйста! Да, я еще прогу неотлаживал, однако в случае нечетного кол-ва элементов алгоритм сохраняется?Я думаю, что да, а вы? :)]]> Ярослав Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528944 Wed, 01 Dec 2004 07:31:42 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528944 Цитата tserega, 30.11.04, 22:02, 528700
Где-то читал, что хорошо себя проявляет модификация quicksort-а, где при небольшом количестве элементов (порядка 10) используется сортировка вставками...

Кхм, скорее всего оно действительно станет работать быстрее, но код резко усложнится, а при количестве порядка 10^5 - 10^6 элементов, это вряд ли сильно повлияет на скорость, хотя надо попробовать

PS Опять таки из олимпиадной практики: достаточно написать обычный qsort и будет счастье =)]]> Kheor Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528700 Tue, 30 Nov 2004 19:02:42 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528700 Цитата Kheor, 29.11.04, 22:22, 527418
qsort в среднем работает ~ в 4 раза быстрее сортировки кучей

Во многом благодаря тому, что все операции очень простые (тоже из олимпиадной практики).
Где-то читал, что хорошо себя проявляет модификация quicksort-а, где при небольшом количестве элементов (порядка 10) используется сортировка вставками...]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528674 Tue, 30 Nov 2004 18:18:09 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528674 Цитата mo3r, 30.11.04, 15:42, 528287
Я оказался неправ.

Цитата mo3r, 30.11.04, 15:42, 528287
Предложенный qsort работает в 2 раза медленнее, чем написанный мною heapsort.

Так ты ведь и говорил, что qsort медленнее работает:
Цитата mo3r, 29.11.04, 19:38, 527232
когда я мерял на совершенно разных входных данных, получалось, что они либо одинаково работают, либо QuickSort медленнее


Покажи свою реализацию heap-sort'а очень интересно посмотреть]]> Kheor Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528287 Tue, 30 Nov 2004 12:42:26 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=528287 mo3r Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527418 Mon, 29 Nov 2004 19:22:52 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527418
    var
        a: array of longint;
        c, i: longint;
     
    procedure qs( l, r: longint);
    var
        i, j, m: longint;
    begin
        i := l;
        j := r;
        m := a[l + random(r - l + 1)]; //тут избавляемся от возможной квадратичной скорости
        while i <= j do begin
            while a[i] < m do inc(i);
            while a[j] > m do dec(j);
            if i <= j then begin
                c := a[i];
                a[i] := a[j];
                a[j] := c;
                inc(i);
                dec(j);
            end;
        end;
        if l < j then qs(l, j);
        if i < r then qs(i, r);
    end;


А, вообще, qsort в среднем работает ~ в 4 раза быстрее сортировки кучей. (это из олимпиадной практики)]]> Kheor Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527299 Mon, 29 Nov 2004 17:51:05 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527299 wormball, нет, я специально делал несколько вариантов и выбрал наилучший. Тот вариант, который в стандартной поставке BP7.0\Examples\DOS\QuickSort.pas даже не принимался в расчет. В принципе, можно повторить замеры производительности. Я постараюсь найти ту программу, которой я пользовался. Кстати, если ты предложишь вариант QuickSort, который будет работать быстрее HeapSort, то это будет очень интересно.]]> mo3r Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527275 Mon, 29 Nov 2004 17:22:38 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527275 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527232 Mon, 29 Nov 2004 16:38:05 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527232 wormball, когда я мерял на совершенно разных входных данных, получалось, что они либо одинаково работают, либо QuickSort медленнее. Причем разница могла быть существенной в зависимости от характера входных данных.]]> mo3r Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527098 Mon, 29 Nov 2004 14:54:24 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=527098
итак, кучей (heap) (не путать с динамической памятью и кучами дерьма) называется такое двоичное дерево, что:
1. значение предка не больше значений потомков.
2. "все веточки примерно одинаковой длины". то есть длины отличаются не более чем на 1.
3. все длинные веточки сгруппированы слева.

например
    кучи
           21
         /    \
       23     48
      /  \   /  \
     37  29 85  48
     
            1
         /    \
        2     3
      /  \
     4   5  
     
    не кучи
           15
         /    \
       23     65 <- 65 больше, чем 48 (нарушение п. 1)
      /  \   /  \
     37  29 85  48
     
             1
           /   \
          2     3
        /  \
       4   5  
     /  \
     6  7    <- ветви оканчиваются на трёх уровнях (нарушение п. 2)
     
           1
         /   \
        2     3
      /        \
     4          5  <- потомки не сгруппированы (нарушение п. 3)

прикол в том, что деревья подобного вида (удовлетворяющие пп. 2 и 3) можно организовать с помощью массива, не прибегая к указателям. например, вышеприведённые кучи будут выглядеть так:
    21 23 48 37 29 85 48
    1 2 3 4 5

, то есть все вершины записываются туда по порядку, начиная с первого уровня. при этом всегда можно восстановить вид дерева, пользуясь свойствами 2 и 3. адреса предков и потомков вершины с номером n будут выражаться так(массив нумеруется с единицы, а не с нуля):
предок(n) = n/2 (или n shr 1) (целочисленное деление на 2)
левый потомок(n) = n*2 (или n shl 1)
правый потомок(n) = n*2+1 (или n shl 1 + 1)

при этом наименьший элемент кучи всегда будет в её начале.

далее. предположим, что мы имеем кучу и хотим добавить к ней один элемент. записываем его в конец кучи, а затем поступаем так: если он меньше своего родителя, то меняем его местами с родителем, потом снова сравниваем, и так пока он не станет на своё место.
    просеивание вверх
           21
         /    \
       23     48
      /  \   /  \
     37  29 85  17<новый елемент
     
           21
         /    \
       23     17<
      /  \   /  \
     37  29 85  48
     
           17<
         /    \
       23     21
      /  \   /  \
     37  29 85  48

таким образом мы вновь получили кучу.
если же, наоборот, новый элемент оказался во главе кучи, надо его менять местами с наименьшим из потомков.
    просеивание вниз
           10<
         /    \
        2     3
      /  \
     4   5  
     
           2
         /  \
       10<   3
      /  \
     4   5  
     
           2
         /  \
        4    3
      /   \
     10<   5
заметьте, сложность обеих вышеописанных операций не более O(ln n). если мы хотим изъять из кучи наименьший элемент, мы берём этот элемент (который всегда будет расположен в вершине) и ставим в вершину кучи, а затем проделываем вышеозначенную операцию.

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

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

Цитата mo3r, 23.11.04, 22:11, 521110
wormball, heap sort всегда работает за O(n*log(n)) в отличие от быстрой сортировки

правильно
Цитата mo3r, 23.11.04, 22:11, 521110
При этом по времени heap sort всегда быстрее quick sort'а

автор книжки мерял, у него получилось, что медленнее]]> wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=521172 Tue, 23 Nov 2004 20:06:05 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=521172 vk Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=521110 Tue, 23 Nov 2004 19:11:40 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=521110
Добавлено
wormball, heap sort всегда работает за O(n*log(n)) в отличие от быстрой сортировки. При этом по времени heap sort всегда быстрее quick sort'а. Особенно это сказывается на массивах следующего вида: очень много элементов, но диапазон их изменения очень мал. Вот здесь quick sort даже медленне, чем bubble sort. Причем, по памяти quick sort тоже более требователен чем heap sort (quick sort требует O(log(n)) в лучшем случае, O(n) в худшем, heap sort - O(1) памяти в худшем случае).]]> mo3r Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=520154 Tue, 23 Nov 2004 07:37:56 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=520154 Цитата

Сортировка с помощью бинарного дерева - это самая тривиальная сортировка, которая только приходит в голову: когда добавляешь новый элемент, то сравниваешь его с элементом вершины и в зависимости от результата сравнения отсылаешь его либо в левую либо в правую ветку (либо оставляешь вместо бывшего верхнего элемента, а его в свою очередь отправляешь либо в лево либо в право) и т. д. пока он не займет нужное место. В случае равномерно распределенных случайных чисел сложность составляет O(N*Log(N)), в худшем случае сложность O(N^2).


Каким же именно образом происходит сравнение элементов? Другими словами: отчего зависит попадание
потомка либо влево, либо вправо, либо на место предка.
Мне известно, что в бинарном дереве потомок слева должен быть меньше своего предка, а потомок справа - наоборот,
больше предка. Тут условия сравнения вполне понятны. Но при каком условии потомок встает на место предка - вот
вопрос?
:wall: Разъясните мне пожалуйста, прогу на неделе сдавать надо...]]> Alto Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92019 Tue, 01 Apr 2003 09:50:49 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92019 Цитата Serega_f1, 28.03.03, 12:34:59
    <br>void HeapSort(int N) {...

...

Все равно, heap sort и сортировка бинарным деревом - это разные вещи.
Теоретически, heap sort должна работать быстрее дерева, поскольку в ней
содержится меньше информации.
]]> S.Yu.Gubanov Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92018 Fri, 28 Mar 2003 09:34:59 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92018
    <br>void HeapSort(int N) {<br> int x;<br> int l=(N/2)+1;<br> int r=N;<br> while (l>0) {l--; shift(l,r); }<br> while (r>0) {<br>   x=mas[0]; <br>   mas[0]=mas[r]; <br>   mas[r]=x;<br>   r--; shift(l,r);<br> }<br>}<br><br>void shift(int l,int r) {<br> int x=mas[l];<br> int i=l;<br> int j=2*l;<br> if ((j<r)&&(mas[j]<mas[j+1])) j++;<br> while ((j<=r)&&(x<mas[j])) {<br>   mas[i]=mas[j];<br>   i=j;   <br>   j=2*j;<br>   if ((j<r)&&(mas[j]<mas[j+1])) j++; <br> }<br> mas[i]=x;<br>}<br>

N - длина массива
так вроде]]> Serega_f1 Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92017 Fri, 28 Mar 2003 07:38:44 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92017
Сортировка с помощью бинарного дерева - это самая тривиальная сортировка, которая только приходит в голову: когда добавляешь новый элемент, то сравниваешь его с элементом вершины и в зависимости от результата сравнения отсылаешь его либо в левую либо в правую ветку (либо оставляешь вместо бывшего верхнего элемента, а его в свою очередь отправляешь либо в лево либо в право) и т. д. пока он не займет нужное место. В случае равномерно распределенных случайных чисел сложность составляет O(N*Log(N)), в худшем случае сложность O(N^2).

Пример
    <br>            7<br>          /   \<br>        5      10<br>       / \     / \<br>      2   6   9  12<br>


]]> S.Yu.Gubanov Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92016 Thu, 27 Mar 2003 15:53:52 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92016 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92015 Thu, 27 Mar 2003 01:04:10 +0000 Сортировка массива при помощи бинарного дерева https://forum.sources.ru/index.php?showtopic=9474&view=findpost&p=92015 Dmitry_K Алгоритмы