Поиск алгоритма сортировки с как можно меньше сравнивает операции

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

To answer this, we need to make a lot of assumptions.

Let's assume we are sorting pictures by cuteness. The goal is to get the maximum usable information from the human in the least amount of time. This interaction will dominate all other computation, so it's the only one that counts.

As someone else mentioned, humans can deal well with ordering several items in one interaction. Let's say we can get eight items in relative order per round.

Each round introduces seven edges into a directed graph where the nodes are the pictures. If node A is reachable from node B, then node A is cuter than node B. Keep this graph in mind.

Now, let me tell you about a problem the Navy and the Air Force solve differently. They both want to get a group of people in height order and quickly. The Navy tells people to get in line, then if you're shorter than the guy in front of you, switch places, and repeat until done. In the worst case, it's N*N comparison.

The Air Force tells people to stand in a square grid. They shuffle front-to-back on sqrt(N) people, which means worst case sqrt(N)*sqrt(N) == N comparisons. However, the people are only sorted along one dimension. So therefore, the people face left, then do the same shuffle again. Now we're up to 2*N comparisons, and the sort is still imperfect but it's good enough for government work. There's a short corner, a tall corner opposite, and a clear diagonal height gradient.

You can see how the Air Force method gets results in less time if you don't care about perfection. You can also see how to get the perfection effectively. You already know that the very shortest and very longest men are in two corners. The second-shortest might be behind or beside the shortest, the third shortest might be behind or beside him. In general, someone's height rank is also his maximum possible Manhattan distance from the short corner.

Looking back at the graph analogy, the eight nodes to present each round are eight of those with the currently most common length of longest inbound path. The length of the longest inbound path also represents the node's minimum possible sorted rank.

You'll use a lot of CPU following this plan, but you will make the best possible use of your human resources.

Из задания, которое я когда-то выполнил по этой самой теме ...

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

Size      QkSort    HpSort   MrgSort     ModQk   InsrtSort
  2500     31388     48792     25105     27646     1554230
  5000     67818    107632     55216     65706     6082243
 10000    153838    235641    120394    141623    25430257
 20000    320535    510824    260995    300319   100361684
 40000    759202   1101835    561676    685937
 80000   1561245   2363171   1203335   1438017
160000   3295500   5045861   2567554   3047186

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

Size      QkSort    HpSort   MrgSort     ModQk   InsrtSort
  2500     72029     46428     16001     70618      76050
  5000    181370    102934     34503    190391    3016042
 10000    383228    226223     74006    303128   12793735
 20000    940771    491648    158015    744557   50456526
 40000   2208720   1065689    336031   1634659  
 80000   4669465   2289350    712062   3820384
160000  11748287   4878598   1504127  10173850

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

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

Вы также можете найти « Minimal Merge Sort » Тадао Такаока, который является более эффективной версией сортировки слиянием.

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

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

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

Было бы тоже интересно написать :)

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

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

Quicksort по сути является однопоточным алгоритмом сортировки .

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

Другой возможностью было бы использовать ранжирование. система, используемая известным веб-сайтом Hot or Not. Это требует гораздо большего количества сравнений, но сравнения могут происходить в любой последовательности и параллельно, это будет работать быстрее, чем классический вид, при условии, что в вашем распоряжении достаточно гуминоидов.

Лучшим вариантом будет сортировка слиянием

Минимальное время выполнения - n * log (n) [База 2] Это реализовано следующим образом:

Если список имеет длину 0 или 1, то он уже отсортирован.

В противном случае:

Разделите несортированный список на два подсписка примерно половиной размера.

Сортировка каждого подсписка рекурсивно, повторно применяя сортировку слиянием.

Объедините два подсписка обратно в один отсортированный список.

На самом деле, эти вопросы вызывают больше вопросов.

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

А как насчет вопросов доверия и ошибки? Не всем можно доверять или делать все правильно - некоторые виды будут катастрофически неправильными, если в какой-то момент вы дадите неправильный ответ на единственное сравнение.

А как насчет субъективности? «Расположите эти фотографии в порядке привлекательности». Как только вы дойдете до этого момента, все может стать действительно сложным. Как заметил кто-то другой, что-то вроде «горячо или нет» концептуально является самым простым, но не очень эффективным. В самом сложном случае я бы сказал, что Google - это способ сортировки объектов по порядку,