Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 17
PS: вопрос не потеме топика. А из какой колоды карта в заголовке статьи? Я бы прикупил колоду %)
Нашёл в Гугл-Картинках по запросу «joker card».
По всей видимости, первоисточник тут. Там, правда только карты с картинками, 2-10 придётся нарисовать самому. Также автор не создавал различные масти, несколько карт нарисовал просто just for fun.
Думаю, можно на основе того что есть «дорисовать» колоду и найти какое-нибудь рекламное агентство, специализирующееся на сувенирной продукции в своём городе, которое напечатает. Было бы время, навыки Фотошопа, деньги и желание.
По всей видимости, первоисточник тут. Там, правда только карты с картинками, 2-10 придётся нарисовать самому. Также автор не создавал различные масти, несколько карт нарисовал просто just for fun.
Думаю, можно на основе того что есть «дорисовать» колоду и найти какое-нибудь рекламное агентство, специализирующееся на сувенирной продукции в своём городе, которое напечатает. Было бы время, навыки Фотошопа, деньги и желание.
Эм. А зачем изобретать сортировку с худшим временем O(n2), если такими же характеристиками обладает сортировка Хоара, но работает быстрее?
Во-первых, информатика ничем не хуже других точных наук. Так же как в математике доказываются все возможные теоремы и леммы (даже если они «бесполезные»), а в физике должны быть открыты все законы (даже если это крайне абстрактные рассуждения о петлевой квантовой гравитации). Так и в информатике, развитие будет происходить, если не успокоиться на быстрой сортировке (раз эффективно — зачем ещё что-то изучать?), а дотошно перебрать и остальные алгоритмы. Что-нибудь где-нибудь когда-нибудь — да пригодится.
Во-вторых, быстрая сортировка — не панацея. Почитайте про «массивы-убийцы» и IntroSort — это интересно.
В-третьих, изучая сортировки, часто ознакамливаешься с методами которые могут пригодиться где-нибудь ещё, необязательно для упорядочивания массивов. В данном случае более подробно изучаем такую полезную в хозяйстве вещь как двоичная куча.
Во-вторых, быстрая сортировка — не панацея. Почитайте про «массивы-убийцы» и IntroSort — это интересно.
В-третьих, изучая сортировки, часто ознакамливаешься с методами которые могут пригодиться где-нибудь ещё, необязательно для упорядочивания массивов. В данном случае более подробно изучаем такую полезную в хозяйстве вещь как двоичная куча.
Устойчивость — Устойчивая
Серьезно? При построении кучи вся «устойчивость» поломается. Неустойчивая она.
Я, может, чего-то недопонимаю, так что рад любым поправкам. Век живи — век учись, как говорится. Очень может быть что я неверно трактую понятие устойчивость алгоритма.
Устойчивость ломается не во время строительства кучи, а в момент когда всплывший в корень максимум меняется местами с последним элементом массива. Всё, в неотсортированной части массива больше не выполняется принцип «родитель больше потомков», сортирующее дерево полетело к чертям, перестраиваем заново. Но обмены максимумов на последние элементы неотсортированных подмассивов происходят в heapsort, но не в jsort.
Сам по себе процесс построения кучи уменьшает энтропию структуры, добавляет ей упорядоченности, во всяком случае, несомненно той части массива, которая ближе к корню сортирующего дерева.
В jsort строится 2 кучи подряд, причём вторая по счёту куча не ломает ту упорядоченность, которая создана первой кучей, ибо обе пирамиды разнонаправленные — одна двигает элементы поменьше в начало, другая — элементы побольше — в конец. Потом сразу сортировка вставками, которая без сомнения, является устойчивой. Или я всё перепутал?
Устойчивость ломается не во время строительства кучи, а в момент когда всплывший в корень максимум меняется местами с последним элементом массива. Всё, в неотсортированной части массива больше не выполняется принцип «родитель больше потомков», сортирующее дерево полетело к чертям, перестраиваем заново. Но обмены максимумов на последние элементы неотсортированных подмассивов происходят в heapsort, но не в jsort.
Сам по себе процесс построения кучи уменьшает энтропию структуры, добавляет ей упорядоченности, во всяком случае, несомненно той части массива, которая ближе к корню сортирующего дерева.
В jsort строится 2 кучи подряд, причём вторая по счёту куча не ломает ту упорядоченность, которая создана первой кучей, ибо обе пирамиды разнонаправленные — одна двигает элементы поменьше в начало, другая — элементы побольше — в конец. Потом сразу сортировка вставками, которая без сомнения, является устойчивой. Или я всё перепутал?
Устойчивость ломается не во время строительства кучи
В том числе и во время строительства.
«2 1 1», первый проход.
//То из левого и правого потомка выбираем наименьшего
if (a[child] >= a[child + 1]) {
child += 1;
}
возьмет вторую единицу и поменяет с двойкой. Все.
Нет, не всё.
Ну, во-первых, в этом месте сравниваются два потомка (1 и 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 обе кучи использованы таким образом, что они двигают ключи в те стороны, откуда они «родом». То есть первая невозрастающая куча передвигает небольшие элементы в начало (где они и должны быть, ибо сортируем по возрастанию), вторая инвертированная неубывающая куча закидывает крупные элементы поближе к концу. Направление, по которым кучи раскидывают элементы совпадает с «общей линией партии».
В heapsort чтобы упорядочить по возрастанию, мы строим неубывающие кучи (чтоб находить максимумы и перекидывать их в конец), то есть, вообще говоря большие элементы перекидываем поближе к корню дерева, то есть к началу массива (а в финале как раз нужно, чтобы всё было наоборот). Чтобы в конечном итоге отсортировать «от меньшего к большему», алгоритм каждый раз пытается расставить элементы «от большего к меньшему». Понятно, что устойчивость и рядом не валялась.
В jsort обе кучи использованы таким образом, что они двигают ключи в те стороны, откуда они «родом». То есть первая невозрастающая куча передвигает небольшие элементы в начало (где они и должны быть, ибо сортируем по возрастанию), вторая инвертированная неубывающая куча закидывает крупные элементы поближе к концу. Направление, по которым кучи раскидывают элементы совпадает с «общей линией партии».
То есть первая невозрастающая куча передвигает небольшие элементы в начало (где они и должны быть, ибо сортируем по возрастанию)
Да, но среди нескольких одинаковых элементвов некоторых она передвинет, а некоторых нет. Причем передвинет не обязательно первых или последних, а каких получится.
Да, передвинет те элементы, которым «повезёт». Но они передвинутся именно в ту сторону, в которую нужно.
... 1a 1b 1c ...
«В нужную сторону» уехала 1b. Как она потом встанет между 1a и 1c?
Устойчивая сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. (Wiki)
Jsort меняет местами одинаковые элементы (приходится это делать, чтобы заглянуть вниз по ветке и посмотреть нет ли там чего интересного), а значит она неустойчивая.
Поэтому Вы правы, а я — нет. Подправил информацию, спасибо что заметили )))
P.S. Не сразу заметил, что определение из Вики Вы указали в одном из предыдущих комментариев. Пора спать )))
Jsort меняет местами одинаковые элементы (приходится это делать, чтобы заглянуть вниз по ветке и посмотреть нет ли там чего интересного), а значит она неустойчивая.
Поэтому Вы правы, а я — нет. Подправил информацию, спасибо что заметили )))
P.S. Не сразу заметил, что определение из Вики Вы указали в одном из предыдущих комментариев. Пора спать )))
Ничего себе «скромный труженик» — первым делом запатентовал свой алгоритм, а теперь занимающийся патентным троллингом на более-менее схожие алгоритмы.… Почитайте — во сколько он оценивает свою лицензию
По-моему, две кучи — просто хорошая подготовка перед сортировкой вставками. С ростом n эффект такой предобработки (в худших случаях) будет всё меньше. По сути, если уже есть сортировка вставками, такая предобработка может повысить скорость работы алгоритма, если сортировка вставками не реализована — лучше не заниматься непотребствами, и реализовывать что-нибудь O(n log n)).
Автору алгоритма, конечно, аригато за сэкономленные наносекунды (понравилась сама идея посмотреть на сортировку вставками «и так, и сяк»), а вот автору топика — спасибо за неустанное бдение в деле совершенствования и демонстрации общественности новых вариантов алгоритмов сортировок.
Автору алгоритма, конечно, аригато за сэкономленные наносекунды (понравилась сама идея посмотреть на сортировку вставками «и так, и сяк»), а вот автору топика — спасибо за неустанное бдение в деле совершенствования и демонстрации общественности новых вариантов алгоритмов сортировок.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
J-сортировка