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

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 карт в каждой. Сортируйте эти две стопки «в руки», затем положите их рядом друг с другом. Объедините их в стопку результатов, всегда кладя нижнюю часть показанных карт в стопку результатов. Вы можете увидеть, какие груды уже отсортированы, оставив их лицом вверх. Обязательно всегда объединяйте стопки одинакового размера, в противном случае продолжайте разбивать следующую несортированную стопку.

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

Answer 2

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

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

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

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

Answer 3

Эрик,

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

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

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

1.) Закажите колоду так, как вы хотите, и дайте каждой карточке знак #.

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

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

pic

4.) Обрезать 1, как показано на карте 1 ниже (правый или младший бит обрезан), также обрезать второй до последнего на карте 2 ...

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

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

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

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

вот как это работает: первая операция (шаг 6) перемещает все нечетные целые числа впередНапример, ставит 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 / и т.д. ... последний ход занимает ~ половину колоды и помещает ее перед другим... и это приводит к полностью упорядоченной колоде за минимальное количество ходов

Cheers, Jeremy

Answer 4

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

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

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

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

Answer 5

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

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

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

Answer 6

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

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