Существуют ли какие-либо худшие алгоритмы сортировки, чем Bogosort (он же Обезьянья сортировка)? [закрытый]

много лет назад я изобрел (но так и не реализовал) MiracleSort.

Start with an array in memory.
loop:
    Check to see whether it's sorted.
    Yes? We're done.
    No? Wait a while and check again.
end loop

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

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

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

EDIT: строго говоря, это не алгоритм, так как он не гарантированно завершится. Разве" не алгоритм "квалифицируется как " худший алгоритм"?

Квантовая Bogosort

алгоритм сортировки, который предполагает, что многомировая интерпретация квантовой механики верна:

1. проверьте, что список отсортирован. Если нет, уничтожьте вселенную.

в конце алгоритма список будет отсортирован в единственной оставшейся Вселенной. Этот алгоритм принимает наихудший случай O(N) и средний случай O (1) Время. На самом деле, среднее количество сравнений выполняется 2: есть 50% шанс, что Вселенная будет уничтожена на втором элементе, 25% шанс, что она будет уничтожена на третьем, и так далее.

сортировка звона, как описано здесь.

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

Я удивлен, что никто еще не упомянул sleepsort... Или я этого не заметил? Так или иначе:

#!/bin/bash
function f() {
    sleep ""
    echo ""
}
while [ -n "" ]
do
    f "" &
    shift
done
wait

пример использования:

./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7

С точки зрения производительности это ужасно (особенно второй пример). Ждать почти 3,5 месяца, чтобы отсортировать 2 числа, это плохо.

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

лучший случай O (N) (первый раз ребенок!) Худший случай O (никогда)

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

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

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

list = someList
while (list not sorted):
    doNothing

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

вот 2 вида я придумал с моим соседом по комнате в колледже

1) Проверьте заказ 2) может быть, случилось чудо, к 1

и

1) проверьте, если это в порядке, если нет 2) Поместите каждый элемент в пакет и отскочите от удаленного сервера обратно к себе. Некоторые из этих пакетов вернутся в другом порядке, поэтому перейдите к 1

Bogobogosort. Да, это вещь. в Bogobogosort, вы Bogosort первый элемент. Проверьте, отсортирован ли этот элемент. Будучи одним из элементов, он будет. Затем добавить второй элемент, и Bogosort этих двух, пока все не образуется. Затем вы добавите еще один элемент, затем Bogosort. Продолжайте добавлять элементы и Bogosorting, пока Вы, наконец, не сделали каждый элемент. Это было спроектировано так, чтобы никогда не преуспеть с каким-либо значительным списком до тепловой смерти Вселенной.

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

for (int n=1; n<sizeof(list); ++n) {
  while (!isInOrder(list, 0, n)) {
    shuffle(list, 0, n);
  }
  if (!isInOrder(list, 0, n+1)) { n=0; }
}

есть такой сорт, который называется богобогосорт. Во-первых, он проверяет первые 2 элемента, и богосортит их. Далее он проверяет первые 3, богосортит их и так далее. Если список не работает в любое время, он перезапускается, снова сортируя первые 2. Регулярные bogosort имеет среднюю сложность о(n!), этот алгоритм имеет среднюю сложность O (N!1!2!3!...Н!) Edit: чтобы дать вам представление о том, насколько велико это число, для 20 элементов этот алгоритм занимает в среднем 3,930093*10^158 лет, значительно выше предполагаемой тепловой смерти Вселенной (если это произойдет) 10^100 лет, тогда как слияние Рода занимает около .0000004 секунды, сортировка пузырьков .0000016 секунд, а богосорт занимает 308 лет, 139 дней, 19 часов, 35 минут, 22,306 секунды, предполагая, что год составляет 365,242 дня, а компьютер выполняет 250,000,000 32-битных целочисленных операций в секунду. Edit2: этот алгоритм не так медленен, как" алгоритм " miracle sort, который, вероятно, как и этот сорт, заставит компьютер засосать черную дыру прежде чем он успешно сортирует 20 elemtnts, но если бы это было так, я бы оценил среднюю сложность 2^(32 (количество бит в 32-битном целочисленном числе) N) (количество элементов)(число

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

в лучшем случае scenerio - O (∞)

Edit выше на основе проницательное наблюдение по KennyTM.

"Что бы ты хотела?- сорт

1. обратите внимание на системное время.
2. сортировка с помощью Quicksort (или что-нибудь еще разумно разумное), опуская самый последний своп.
3. обратите внимание на системное время.
4. рассчитать необходимое время. Расширенная точность арифметики является требованием.
5. подождите необходимое время.
6. выполните последнюю замену.

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

ничто не может быть хуже, чем бесконечность.

Bozo sort-это связанный алгоритм, который проверяет, отсортирован ли список, и, если нет, меняет местами два элемента случайным образом. Он имеет те же самые лучшие и худшие показатели, но я интуитивно ожидаю, что средний случай будет длиннее, чем Богосорт. Трудно найти (или произвести) какие-либо данные о производительности этого алгоритма.

в худшем случае производительность O (∞) может даже не сделать его алгоритмом в соответствии с некоторые.

алгоритм-это всего лишь ряд шагов, и вы всегда можете сделать хуже, немного изменив его, чтобы получить желаемый результат в большем количестве шагов, чем это было ранее. Можно было бы намеренно поместить знание о количестве шагов, предпринятых в алгоритм, и заставить его прекратить и произвести правильный вывод только после X количество шагов было сделано. Что X вполне может быть порядка O (n²) или O (n^n!) или все, что алгоритм хотел сделать. Это эффективно увеличило бы его наилучшие, а также средние границы случая.

но ваш худший сценарий не может быть увенчан:)

сегменты π

предположим, что π содержит все возможные комбинации конечных чисел. Смотрите математика.stackexchange вопрос

1. определите количество цифр, необходимых из размера массива.
2. используйте сегменты π мест в качестве индексов, чтобы определить, как изменить порядок массива. Если сегмент превышает границы размера для этого массива, отрегулируйте π десятичное смещение и начните сначала.
3. проверьте, если повторно упорядоченный массив сортируется. Если это woot, то еще отрегулируйте смещение и начните заново.

мой любимый медленный алгоритм сортировки-это сортировка марионетки:

void stooges(long *begin, long *end) {
   if( (end-begin) <= 1 ) return;
   if( begin[0] < end[-1] ) swap(begin, end-1);
   if( (end-begin) > 1 ) {
      int one_third = (end-begin)/3;
      stooges(begin, end-one_third);
      stooges(begin+one_third, end);
      stooges(begin, end-one_third);
   }
}

в худшем случае сложность O(n^(log(3) / log(1.5))) = O(n^2.7095...).

другой алгоритм медленной сортировки на самом деле называется slowsort!

void slow(long *start, long *end) {
   if( (end-start) <= 1 ) return;
   long *middle = start + (end-start)/2;
   slow(start, middle);
   slow(middle, end);
   if( middle[-1] > end[-1] ) swap(middle-1, end-1);
   slow(start, end-1);
}

это O(n ^ (log n)) в лучшем случае... даже медленнее, чем stoogesort.

Recursive Bogosort (probably still O(n!){
if (list not sorted)
list1 = first half of list.
list 2 = second half of list.
Recursive bogosort (list1);
Recursive bogosort (list2);
list = list1 + list2
while(list not sorted)
    shuffle(list);
}

эта страница представляет собой интересное чтение по теме:http://home.tiac.net / ~cri_d/cri/2001/badsort.html

мой личный фаворит-это sillysort Тома Даффа:

/*
 * The time complexity of this thing is O(n^(a log n))
 * for some constant a. This is a multiply and surrender
 * algorithm: one that continues multiplying subproblems
 * as long as possible until their solution can no longer
 * be postponed.
 */
void sillysort(int a[], int i, int j){
        int t, m;
        for(;i!=j;--j){
                m=(i+j)/2;
                sillysort(a, i, m);
                sillysort(a, m+1, j);
                if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; }
        }
}

двойной bogosort

Bogosort дважды и сравнить результаты (просто чтобы убедиться, что это занимает), если не сделать это снова

вы можете сделать любой алгоритм сортировки медленнее, запустив свой шаг" is it sorted " случайным образом. Что-то вроде:

1. создайте массив булевых значений того же размера, что и сортируемый массив. Установите их все в false.
2. запустите итерацию bogosort
3. выберите два случайных элементов.
4. если два элемента отсортированы по отношению друг к другу (i
5. проверьте, если все логические значения в массиве являются истинными. Если нет, вернитесь к 3.
6. сделано.

Да, SimpleSort, в теории он работает в это эквивалентно O(...9999) что, в свою очередь, эквивалентно O(∞ - 1), что, как это происходит, также эквивалентно O(∞). Вот мой пример реализации:

/* element sizes are uneeded, they are assumed */
void
simplesort (const void* begin, const void* end)
{
  for (;;);
}

http://richardhartersworld.com/cri_d/cri/2001/badsort.html, который говорит, что средний случай, вероятно, где-то около O(n^3) или O(n^2 log n) (он не совсем уверен).

Я думаю, что можно было бы сделать это более эффективно, потому что я думаю, что можно было бы сделать разворот работа в O (1) раз.

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

Randomsubsetsort.

учитывая массив из n элементов, выберите каждый элемент с вероятностью 1 / n, рандомизируйте эти элементы и проверьте, отсортирован ли массив. Повторяйте, пока не отсортированы.

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