Эзотерические сортировки Дэвида Морган-Мара

[@Conung_ViC]

Первые алгоритмы хоть как то сортируют, а «разумный замысел» — выше человеческого понимания -) Надо было назвать «Божественным замыслом»

[@valemak]

Зато у неё сложность O(1).

[@Aniro]

O(0) же, что ещё раз подтверждает абсолютное совершенство.

[@zagayevskiy]

Кто не понял алгоритм, вот вам реализация

В этом месте под спойлером я ожидал увидеть brainfuck=)

[@Mrrl]

Сортировка на BF оказалась совсем несложной:

[>]>>>>>+
[-<<<<<<[<]>[-<+>]>
  [
    [-<+>]<<<<<+[>>>->->+[<]<<]-[+<-]>>>
    [>>[>]>[-]+<<[<]<[->+<]]
    >>[-<+<<<<+>>>>>]> 
  ]
  <<[-<<<+>>>]>>>
]

Правда, это обычный пузырёк…

[@Mrrl]

А «Джаред Даймонд» это разве не обычный sleepsort?

[@valemak]

Да и «Демон Максвелла» от quicksort не сильно отличается :)

[@valemak]

Единственное отличие — в sleepsort чем больше максимальный элемент, тем дольше будет сортироваться. В «Джареде Даймонде» наоборот.

[@Davidov]

Если, как написано в тексте, использовать массив, то сложность Dropsort, вроде, O(n*n). А вот если двусвязный список, то тогда действительно O(n).

[@valemak]

Вообще-то да, при каждом сбросе из массива сдвиг оставшихся элементов влево приводит к итоговому O(n²).

Конечно же, так выгодно обрабатывать список, а не массив.

[@Nikelandjelo]

Да не, вроде можно и за O(n) на массиве. Если хранить 2 указателя: на текущий элемент и на последний «проверенный и не удалённый» и проверяя их между собой на каждому шаге. В конце надо будет только создать новый массив и скопировать туда все оставшиеся элементы, но это всё равно O(n).

[@Davidov]

Ну да, если не in-place, то вроде можно за O(n). Согласен.

[@NickLion]

in-place:

#include <iostream>
#include <ctime>
#include <cstdlib>

int main()
{
    int n = 10;
    int* a = new int[n];
    std::srand(std::time(NULL));
    for (int i = 0; i < n; i++) {
        a[i] = std::rand() % 10;
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
    // dropsort
    int j = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] >= a[j]) {
            j++;
            if (j < i)
                a[j] = a[i];
        }
    }
    n = j + 1;
    // end of dropsort
    for (int i = 0; i < n; i++)
        std::cout << a[i] << " ";
    std::cout << std::endl;
    return 0;
}

[@linoleum]

Спасибо, интересно.
Очень понравился Dropsort:)