Как эффективно * почти * отсортировать список?

Question

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

Как я могу сделать это наиболее эффективно?

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

_{Контекст реализует почти жадныйпоиск путем введения очень незначительного элемента неточности;это в узком цикле, и поэтому скорость сортировки и вызова random() должна рассматриваться как}

Мой текущий код должен сделать std::sort (это C ++), а затем выполнить оченькороткое перемешивание только в начале массива:

for(int i=0; i<3; i++) // I know I have more than 6 elements
    std::swap(order[i],order[i+rand()%3]);

Answer 1

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

---

Существует подход, который (в отличие от неполной JSort) позволяет лучше контролировать результирующую случайность и имеет сложность по времени, зависящую от случайности (чем больше случайного результата, тем меньше сложность по времени). Используйте heapsort с Soft heap . Для подробного описания мягкой кучи см. pdf 1 или pdf 2 .

Answer 2

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

for M iterations
  pick a random index i
  pick a random index k
  if (i<k)!=(array[i]<array[k]) then swap(array[i],array[k])

M контролирует «сортировку» массива - при увеличении M массив становится все более и более отсортированным. Я бы сказал, что разумным значением для M является n ^ 2, где n - длина массива. Если вы выбираете случайные элементы слишком медленно, вы можете заранее рассчитать их индексы. Если метод все еще слишком медленный, то вы всегда можете уменьшить M за счет получения более плохой сортировки.

Answer 3

Разделите список на две части одинакового размера.Сортируйте каждую часть отдельно, используя любой обычный алгоритм.Затем объедините эти части.Выполните несколько итераций слияния как обычно, сравнивая слитые элементы.Для других итераций слияния не сравнивайте элементы, а вместо этого выберите элемент из той же части, что и на предыдущем шаге.Нет необходимости использовать ГСЧ, чтобы решить, как обрабатывать каждый элемент.Просто игнорируйте порядок сортировки для каждого N-го элемента.

Другой вариант этого подхода почти сортирует массив почти на месте .Разбейте массив на две части с нечетными / четными индексами.Сортировать их.(Можно даже использовать стандартный алгоритм C ++ с соответствующим образом модифицированным итератором, таким как boost :: permutation_iterator).Зарезервируйте ограниченное пространство в конце массива.Объединяйте части, начиная с конца.Если объединенная часть собирается перезаписать один из не объединенных элементов, просто выберите этот элемент.В противном случае выберите элемент в отсортированном порядке.Уровень случайности определяется количеством зарезервированного пространства.

Answer 4

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

Например, если данные для сортировки - это простое символьное поле Name[N], тогда добавьте поле (при условии, что данные находятся в структуре или классе) с именем NameMod[N].Заполните NameMod с копией Name, но добавьте некоторую рандомизацию.Затем 3% времени (или некоторая соответствующая сумма) меняют первый символ имени (например, меняйте его на +/- один или два символа).И затем в 10% случаев меняются вторые символы +/- на несколько символов.

Затем выполните любой алгоритм сортировки, который вы предпочитаете.Преимущество состоит в том, что вы можете легко изменить эти проценты и случайность.И алгоритм сортировки все еще будет работать (например, у него не будет проблем с функцией сравнения, возвращающей противоречивые результаты).

Answer 5

Вы могли бы использовать стандартный алгоритм сортировки (доступна ли стандартная библиотека?) И передать предикат, который «знает», учитывая два элемента, которые меньше других, или если они равны (возвращая -1, 0 или1).Затем в предикате введите редкий (настраиваемый) случай, когда ответ является случайным, используя случайное число:

псевдокод:

if random(1000) == 0 then
  return = random(2)-1   <-- -1,0,-1 randomly choosen

Здесь у нас есть 1/1000 шансов на «мошенничество».«два элемента, но это число строго зависит от размера вашего контейнера для сортировки.

Еще одна вещь, которую нужно добавить в случае 1000, может состоять в том, чтобы удалить« правильный »ответ, поскольку это не приведет к изменению результата!

Редактировать:

if random(100 * container_size) == 0 then <-- here I consider the container size
{
   if element_1 < element_2
      return random(1); <-- do not return the "correct" value of -1
   else if element_1 > element_2
      return random(1)-1; <-- do not return the "correct" value of 1
   else
      return random(1)==0 ? -1  : 1; <-- do not return 0
}

в моем псевдокоде: random (x) = y, где 0 <= y <= x </p>

Answer 6

Если вы уверены, что элемент находится не дальше k от того места, где он должен быть, вы можете уменьшить сложность времени сортировки N log(N) до N log(k) ....

edit

В частности, вы должны создать k блоков, каждый из которых содержит N / k элементов.

Вы можете выполнить быструю сортировку для каждого сегмента, что занимает k * log(k) раз, изатем сортируйте N/k сегментов, что занимает N/k log(N/k) времени.Умножая эти два, вы можете выполнить сортировку в N log(max(N/k,k))

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

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

, но я не думаю, что вы имели в виду какие-либо ограничения.

Answer 7

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

Это в основном O (n), предполагая, что небольшая начальная сортировка подмножества не займет много времени. Надеюсь, вы сможете построить карту так, чтобы смета могла быть быстро извлечена.

Answer 8

Bubblesort на помощь!

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

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