Эффективные способы сортировки колоды реальных карт

Question

Мне часто приходится сортировать колоды карт. Это «коллекционные» карты, пронумерованные от 1 до 216, а также дубликаты и недостающие номера.

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

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

Мой обычный подход - сделать первое сканирование через колоду и поместить их в стеки 1-49, 50-99, 100-149, 150-199, 200+. Затем я просматриваю каждую колоду и кладу ее в стопки 0, 1, 2, 3, 4. И, наконец, я применяю сортировку вставки для каждого 10-пакета. Однако это остается утомительным процессом.

Другая идея - взять 50 стеков и отсортировать их примерно. 25 будет идти по середине, 40 где-то ближе к концу стека и так далее. Это быстро приносит грубо отсортированную 50-колоду, и я могу легко просканировать ее и исправить сортировку.

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

Answer 1

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

Вы проходите через палубу и кладете все карты меньше 100 на левую кучу, все больше на правой куче. Затем вы сначала берете груды, сначала глубину (так что вы не имеете слишком много кучек сразу). На некотором пороге (возможно, около 5 карт) вы просто сортируете «в руке» (по-видимому, похоже на сортировку вставки). Наконец, вы складываете сваи.

Вы также можете выполнить сортировку слияния: разделите кучу на две части, сначала запишите глубину, пока не прибудете две сваи по 5 карт. Сортируйте эти две сваи «в руке», затем положите их лицом вверх бок о бок. Объедините их в кучу результата, всегда ставя нижнюю из отображающих карточек в кучу результата. Вы можете видеть, какие свай уже отсортированы, оставив их лицом вверх. Обязательно всегда объединяйте сваи одинакового размера, иначе переходите к разделению следующей несортированной кучи.

Редактирование: сортировка по методу radix также может быть хорошей: положите карты на десять свай по их последней цифре, соедините эти сваи в порядке. Затем положите карты на десять свай по их второй до последней цифре, соедините их вместе в порядке еще раз. Наконец, поместите их в груды своей третьей до последней цифрой (в соответствии с вашим описанием, то есть первой цифрой) и соедините их вместе. В конце концов, это может быть проще всего, и это O (n) (вам нужно три прохода через колоду).

Answer 2

Я думаю, что counting sort вместе с вашим методом сортировки вставки могут работать хорошо: сканировать их и ставить их сначала, затем два и так далее.

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

Answer 3

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

Например, было не более 100 карт, пронумерованных 1-100, представьте, что ваша рабочая поверхность разделена на прямоугольную сетку 10 x 10; то, как только каждая карта обрабатывается, введите, например, карту 67 в 7-й столбе 6-й строки. Как только все карты выложены, подберите их в порядке.

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

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

Answer 4

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

Есть трюки, чтобы ускорить сортировку ковша. Большую часть времени в сортировке человеческого ведра затрачивается на вычисление ведра для следующего предмета. Вы можете попробовать два трюка. Во-первых, вы можете сортировать ведро по цифре, что, я думаю, называется сортировкой radix, так что вам никогда не придется сравнивать числа. На первом этапе используются три ведра, которых не так много, но они могут быть в порядке. Второй этап - «основная» работа с десятью ведрами. На третьем этапе вы сортируете десять пронумерованных карточек, а здравый смысл предлагает сортировку вставки. Но даже на этом этапе сортировка радикса может ускорить работу, хотя в каждом ковше только одна карта. Конечно, вы не должны использовать «ведра» с четырьмя сторонами, а просто груды карточек на столе. Вы бы использовали только метод bucket для цифры единиц, если легко подметать карты по порядку. Возможно, для средней ступени слот с тремя сторонами будет работать лучше, чем открытая куча карт.

Второй трюк - обозначить местоположения на столе от 0 до 9, чтобы вы могли быстрее найти правильную кучу. Этикетки можно наклеить на стол, чтобы вы могли их повторно использовать.

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

Answer 5

Эрик,

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

Если у вас есть возможность использовать дырокол и изменить край колоды карт, то для упорядочивания всей сваи в log2 (#of-карты) можно использовать метод сортировки. Таким образом, для ~ 200 карт потребуется 8 операций.

Один из способов я нашел работал хорошо выглядит следующим образом:

1.) Заказать палубе так, как вы хотите, и дать все карты #.

2.) Преобразуйте это # ​​в двоичный файл на длину log2 (количество карточек). , например. log2 (216) ~ 8, то вам нужно будет только 8 мест ... так 0x0 станет 00000000

3.) базовой станции каждую карту с его двоичное представление, как на картинке ниже

рис

4.) Выровняйте 1 выход, как на карте 1 ниже (правый или LSB обрезается), вторая и последняя на карте 2 также обрезается ...

5.) Захватите гвоздь или вязание игла или прямая вешалка и т. д. упаковать колоду вместе (неупорядоченно) с отверстиями, все выровненные

6.) вставьте иглу через отверстие правой руки на всей колоде (или в двоичном разряде). поднимите иглу и позвольте картам, которые не имеют кольца на этой вкладке (вы разрезаете ее), падают в коробку. Переместите карты, зацепившиеся за иглу, в передней части колоды. ** НЕ ИЗМЕНЯЙТЕ ЗАКАЗ НЕЗАКОННЫХ КАРТОЧКОВ, ПОДНИМАЮЩИХ ВЫБРАННЫЕ КАРТЫ. держите палубу в коробке с коробкой с закрытыми отверстиями или что-то подобное

7.) Снова установите палубу, на этот раз используйте иглу на ранее используемом соседнем отверстии (второе справа). сделайте то же самое, пусть неприкрепленные/невыделенные карты попадут в коробку и повторите.

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

вот как это работает: первая операция (этап 6) перемещает все нечетные intgers на фронт, например, ставит 1 перед 2, 3 перед 4 и т. д.

второй ход (1/2 перед 3/4) и 5/6 перед 7/8. Третий ход перемещается 1/2/3/4 перед 5/6/7/8 и 9/10/11/12 перед 13/14/15/16 .. Четвертая операция перемещается 1/2/3/4/5/6/7/8 перед 9/10/11/12/13/14/15/16/ и т. Д. последний ход занимает ~ одну половину колоды и помещает его спереди другие ... и это приводит к полностью упорядоченной палубе в минимальном количестве ходов

Приветствия, Джереми

Answer 6

Я наткнулся на этом пост, потому что я хотел быстро сортировать регулярную колоду из 52 игральных карт , Небольшое экспериментирование предполагает, что я могу сортировать всю колоду примерно в 1:30, используя алгоритм обработки каждой карты в кучу для каждого костюма, а затем вставку сортировать по одному костюму за раз (практически без практики, поэтому я уверен, что это может быть сделано быстрее с практикой).

Я пробовал несколько разных подходов, включая красно-черную раскол, а затем раскалывал красных и чернокожих в свои костюмы, а затем делал вставку по костюмам, но это было заметно медленнее. Я также попытался разбить каждый костюм на 2-7,8-A, чтобы увидеть, была ли сортировка вставки на небольших группах карт быстрее, но она также заметно медленнее. Таким образом, мой забор не тратит время на чрезмерную рекурсию, чтобы сделать брокер.

Экстраполируя этот метод на свои карты, кажется, что наилучшим подходом является обращение к картам в ведра размера, которые вам легко отсортировать сразу (10 или 20 карт, возможно, так как это легко понять из какого ковша они входят), затем выполните сортировку вставки на ведрах. Предположительно, вы должны иметь возможность сортировать свои 216 карточные колоды примерно через 6-7 минут таким образом.