Pull to refresh

Comments 17

PS: вопрос не потеме топика. А из какой колоды карта в заголовке статьи? Я бы прикупил колоду %)
Нашёл в Гугл-Картинках по запросу «joker card».

По всей видимости, первоисточник тут. Там, правда только карты с картинками, 2-10 придётся нарисовать самому. Также автор не создавал различные масти, несколько карт нарисовал просто just for fun.

Думаю, можно на основе того что есть «дорисовать» колоду и найти какое-нибудь рекламное агентство, специализирующееся на сувенирной продукции в своём городе, которое напечатает. Было бы время, навыки Фотошопа, деньги и желание.
Эм. А зачем изобретать сортировку с худшим временем O(n2), если такими же характеристиками обладает сортировка Хоара, но работает быстрее?
Во-первых, информатика ничем не хуже других точных наук. Так же как в математике доказываются все возможные теоремы и леммы (даже если они «бесполезные»), а в физике должны быть открыты все законы (даже если это крайне абстрактные рассуждения о петлевой квантовой гравитации). Так и в информатике, развитие будет происходить, если не успокоиться на быстрой сортировке (раз эффективно — зачем ещё что-то изучать?), а дотошно перебрать и остальные алгоритмы. Что-нибудь где-нибудь когда-нибудь — да пригодится.

Во-вторых, быстрая сортировка — не панацея. Почитайте про «массивы-убийцы» и IntroSort — это интересно.

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

Серьезно? При построении кучи вся «устойчивость» поломается. Неустойчивая она.
Я, может, чего-то недопонимаю, так что рад любым поправкам. Век живи — век учись, как говорится. Очень может быть что я неверно трактую понятие устойчивость алгоритма.

Устойчивость ломается не во время строительства кучи, а в момент когда всплывший в корень максимум меняется местами с последним элементом массива. Всё, в неотсортированной части массива больше не выполняется принцип «родитель больше потомков», сортирующее дерево полетело к чертям, перестраиваем заново. Но обмены максимумов на последние элементы неотсортированных подмассивов происходят в heapsort, но не в jsort.

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

В jsort строится 2 кучи подряд, причём вторая по счёту куча не ломает ту упорядоченность, которая создана первой кучей, ибо обе пирамиды разнонаправленные — одна двигает элементы поменьше в начало, другая — элементы побольше — в конец. Потом сразу сортировка вставками, которая без сомнения, является устойчивой. Или я всё перепутал?
Устойчивость ломается не во время строительства кучи

В том числе и во время строительства.
«2 1 1», первый проход.
                 //То из левого и правого потомка выбираем наименьшего
                if (a[child] >= a[child + 1]) {
                    child += 1;
                }

возьмет вторую единицу и поменяет с двойкой. Все.
Нет, не всё.

Ну, во-первых, в этом месте сравниваются два потомка (1 и 1). Двойка тут не при делах.

Во-вторых, в этом же месте не происходит перестановка, а всего-навсего выбирается тот из потомков который поменьше (запоминается его индекс).

В-третьих, обмен происходит (если происходит) сразу после выбора наименьшего потомка:
            //Родитель меньше потомков?
            if (T < a[child]) {
                
                //Тогда с этим родителем и его потомками разобрались
                done = true;
            
            //Родитель НЕ меньше чем наименьший из его потомков.
            //Перемещаем потомка на место родителя
            //и с родителем в цикле сравниваем уже потомков этого потомка			
            } else {			

                a[parent] = a[child];
                parent = child;
                child = 2 * (parent + 1) - 1;
                
            }


В данном случае двойка обменяется со второй единицей, то есть продвинется в «своём» направлении.

В данном случае двойка обменяется со второй единицей, то есть продвинется в «своём» направлении.

С этим я не спорю, но вторая еденица обгонит первую.

На всякий случай:
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. (с) Wikipedia


Исходный массив:
2 1a 1b


Отсортированный устойчивой сортировкой:
1a 1b 2


Отсортированный JSort (1b поменялся с 2):
1b 1a 2
Ах да, ещё нюанс.

В heapsort чтобы упорядочить по возрастанию, мы строим неубывающие кучи (чтоб находить максимумы и перекидывать их в конец), то есть, вообще говоря большие элементы перекидываем поближе к корню дерева, то есть к началу массива (а в финале как раз нужно, чтобы всё было наоборот). Чтобы в конечном итоге отсортировать «от меньшего к большему», алгоритм каждый раз пытается расставить элементы «от большего к меньшему». Понятно, что устойчивость и рядом не валялась.

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

Да, но среди нескольких одинаковых элементвов некоторых она передвинет, а некоторых нет. Причем передвинет не обязательно первых или последних, а каких получится.
Да, передвинет те элементы, которым «повезёт». Но они передвинутся именно в ту сторону, в которую нужно.
... 1a 1b 1c ...


«В нужную сторону» уехала 1b. Как она потом встанет между 1a и 1c?
Устойчивая сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. (Wiki)

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

Поэтому Вы правы, а я — нет. Подправил информацию, спасибо что заметили )))

P.S. Не сразу заметил, что определение из Вики Вы указали в одном из предыдущих комментариев. Пора спать )))
Ничего себе «скромный труженик» — первым делом запатентовал свой алгоритм, а теперь занимающийся патентным троллингом на более-менее схожие алгоритмы.… Почитайте — во сколько он оценивает свою лицензию
Очень интересно ))) Ссылку на источник информации дайте, люблю запатентованные сортировки )))
По-моему, две кучи — просто хорошая подготовка перед сортировкой вставками. С ростом n эффект такой предобработки (в худших случаях) будет всё меньше. По сути, если уже есть сортировка вставками, такая предобработка может повысить скорость работы алгоритма, если сортировка вставками не реализована — лучше не заниматься непотребствами, и реализовывать что-нибудь O(n log n)).
Автору алгоритма, конечно, аригато за сэкономленные наносекунды (понравилась сама идея посмотреть на сортировку вставками «и так, и сяк»), а вот автору топика — спасибо за неустанное бдение в деле совершенствования и демонстрации общественности новых вариантов алгоритмов сортировок.
Only those users with full accounts are able to leave comments. Log in, please.