Codegolf - Сортировка Для Бозо

Введение

Эта задача касается трех (плохих) алгоритмов сортировки:

 
 56781234 7 10 7 
 

Bogosort works by completely shuffling the array randomly and checking if it becomes sorted (ascending). If not, repeat.

87654321 1000000 100 1 37485612 9050000 9000 10 12345678 0 0 0 28746351 4344 5009 5 18437256 10000 523 25 15438762 10000 223 34 18763524 58924 23524 5 34652817 9283 21 445 78634512 5748 234 13 24567351 577 24 34 works by selecting two elements, randomly, and swapping them. Repeat until sorted (ascending).

Bogosmart works by selecting two elements, randomly, and only swapping them if it makes the array closer to being sorted (ascending), ie. if the element with the lower index was originally larger than the one with the higher. Repeat until sorted.

Вызов

В этой задаче исследуется эффективность (или отсутствие) каждого из этих трех алгоритмов сортировки. Кодекс игры в гольф будет

1. сгенерировать перетасованный массив из 8 элементов целых чисел от 1 до 8 включительно (продолжайте читать, чтобы узнать, как это делать);

2. применить каждый алгоритм к этому массиву; и

3. отобразите исходный массив, за которым следует количество вычислений, необходимое для каждого алгоритма, разделенное одним пробелом (конечный пробел ок), в формате Bogoswap .

Программа создаст 10 тестовых случаев; вы можете сгенерировать все десять вначале или сгенерировать по одному, как угодно. Пример вывода ниже.

Подробности:

Для Bogosort , it should record the number of times the array was shuffled.

Для <ARRAY> <BOGOSORT> <BOGOSWAP> <BOGOSMART> , it should record the number of swaps made.

Для Bogosmart , it should record the number of swaps made.

Пример вывода:

Я выдумал эти цифры; конечно, ваша программа выведет другой результат, но в том же формате.

Правила

• Вся случайность, используемая в вашей программе, должна исходить от доступных вам генераторов псевдослучайных чисел и в противном случае не должна тщательно вычисляться вами. Вам не нужно беспокоиться о семенах.
• Программы не имеют ограничений по времени.
• Массивы должны быть отсортированы по возрастанию.
• Завершающие пробелы или дополнительная новая строка не имеют большого значения.
• Для Bogosort , the array is to be shuffled using any unbiased shuffling algorithm such as Fisher-Yates or Кнут перетасовывает, прямо указано в вашем объяснении. Встроенные методы перетасовки не допускаются. Сгенерируйте тестовые массивы таким же образом.
• Если после перетасовки или замены массив остается прежним, он все равно учитывается и должен быть включен в счет программы. Например, перетасовка массива сама по себе считается перетасовкой, а замена элемента самим собой считается перестановкой, даже если ни одна из этих операций не меняет массив.
• Если мне не изменяет память, массив из 8 элементов не должен занимать слишком много времени для любого из трех алгоритмов. На самом деле, я несколько раз подумал о массиве из 10 элементов, когда попробовал: Bogosmart only required a few thousand (or less) actual shuffles and well under 10 seconds.
• Ваш код должен фактически сортировать массивы, а не просто выдавать ожидаемые значения или математические вычисления для ожидаемого ответа.
• Это соревнование по кодированию, поэтому побеждает самая короткая программа в байтах.

Вот несколько примеров шагов для каждого алгоритма сортировки:

В этом случае программа выведет Bogosort , and then do the same thing 10 times. You do not have to print the arrays while sorting is going on, but I gave the above sample steps so you can understand how each algorithm works and how to count computations.

#код-гольф #случайный #сортировка

Пиф, 62 60 байт

 
 
 
 
 
 
 
 
 <pre id=O></pre> 
 
 
 
 
 
 
 
 

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

Пример вывода будет:

Объяснение:

Моя функция перемешивания использует встроенную функцию jd[ [ put all 4 values in a list jd join by spaces and print . Basically I assign each element of the list a random number of the interval fqZ=Xb*>F=NO.Cb2N)0 .Cb2 give all possible pairs of elements of b O take a random one =N assign it to N >F N check if N[0] > N[1] * N multiply the boolean with N Xb ) swap the two (or zero) values in b = and assign to b f 0 repeat ^ until: qZ Z == b and give the number of repeats и отсортируйте список по ним. Это дает мне беспристрастную случайную перетасовку.

Внешний цикл

fqZ=XJO.CJ2)0 .CJ2 give all possible pairs of elements of J O take a random one XJ ) swap these two elements in J = and store the result in J f 0 repeat ^ until: qZ K Z == K and give the number of repeats at the start repeats the following code 10 times.

Подготовка

Богосорт

Богосвап

Богосмарт

Печать

JavaScript (ES6), 319 345

Неудивительно, что это довольно долго.

За случайное перетасовывание заслуги @core1024 (лучше, чем у меня для того же челленджа)

Проверьте запуск фрагмента (только Firefox, как обычно)