Библиотечная сортировка

[aamonster]

Жду статьи об оптимизации bogosort.
[irony]

[valemak]

И она будет :)

[hdfan2]

Непонятно, для чего выдумывать настолько бесполезный алгоритм. Только чтобы был алгоритм имени тебя? Сортировка вставками для маленьких списков будет столь же эффективна (учитывая необходимое для библ. сортировки копирование данных в конце выполнения), а для больших списков с quicksort'ом ему тягаться не получится. Есть ли для него хоть какое-то применение?

[valemak]

Лично я алгоритмы разбираю just for fun. Реализация модифицированного бинарного поиска и полной перебалансировки массива доставили мне некоторое удовольствие.

Что касается мотивов, которыми руководствовались авторы сортировки — спросите у них. Я привёл персональные странички профессоров на сайтах их университетов, там есть электронные адреса.

[aamonster]

(offtopic)
Для just for fun — алгоритм вычисления "бегущего максимума" (Sliding window minimum/maximum algorithm) знаете? Ну, который обрабатывает массив длины n за O(n) независимо от длины окна?
Интересен тем, что до него додумались довольно поздно, где-то в 80-х.

Если не знаете — вам повезло, можете попробовать додуматься до него самостоятельно.

[valemak]

Спасибо, я погляжу. И даже посмотрю, можно ли этот метод использовать для сортировки. Если да, то отлично: после сортировок вставками будут сортировки выбором, и этот алгоритм органично впишется в этот класс.

[force]

Вообще, использовать этот алгоритм можно для реализации различных SortedList, когда данные добавляются и удаляются и каждый раз перестраивать массив накладно, поэтому нужны специальные дырки для заполнения.
Правда, имхо, гораздо более эффективно в этом случае использовать B-Tree