Программистское
Jan. 6th, 2009 09:12 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkСегодня впервые прочитал о неизвестном мне ранее алгоритме сортировки smoothsort.
Этот алгоритм, разработанный Дейкстрой в 1981 году - вариант сортировки heapsort, отличающийся тем, что время его работы зависит от степени первоначальной отсортированности массива и плавно меняется от O(n) в лучшем случае до O(n log n) в худшем. Английская Википедия мягко замечает, что он используется редко из-за сложности алгоритма. Русская, впрочем, отмечает сложность в реализации как недостаток самого heapsort, а о smoothsort и не заикается.
Интересующимся предлагается ознакомиться с оригинальным текстом Дейкстры (16 страниц довольно слепого скана) или с HTML-транскрипцией - безотносительно к смысловой части алгоритма занимательно стилем изложения - или с реализациями: этой (С) или этими (C++, Delphi) и попробовать перевести на русский (или английский, FWIW) язык предложение "Trinkles the stretches when the adjacent stretches are already trusty."
Более сложного алгоритма сортировки мне не встречалось.
Этот алгоритм, разработанный Дейкстрой в 1981 году - вариант сортировки heapsort, отличающийся тем, что время его работы зависит от степени первоначальной отсортированности массива и плавно меняется от O(n) в лучшем случае до O(n log n) в худшем. Английская Википедия мягко замечает, что он используется редко из-за сложности алгоритма. Русская, впрочем, отмечает сложность в реализации как недостаток самого heapsort, а о smoothsort и не заикается.
Интересующимся предлагается ознакомиться с оригинальным текстом Дейкстры (16 страниц довольно слепого скана) или с HTML-транскрипцией - безотносительно к смысловой части алгоритма занимательно стилем изложения - или с реализациями: этой (С) или этими (C++, Delphi) и попробовать перевести на русский (или английский, FWIW) язык предложение "Trinkles the stretches when the adjacent stretches are already trusty."
Более сложного алгоритма сортировки мне не встречалось.
