@valemak10 июл 2018 в 03:45

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

16 мин

14K

PHP * Алгоритмы * Визуализация данных * Ненормальное программирование * Программирование *

Комментарии 7

@aamonster 10 июл 2018 в 05:22

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

@valemak 10 июл 2018 в 05:28

И она будет :)

@hdfan2 10 июл 2018 в 06:14

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

@valemak 10 июл 2018 в 06:24

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

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

@aamonster 10 июл 2018 в 08:42

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

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

@valemak 10 июл 2018 в 10:52

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

@force 10 июл 2018 в 13:59

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий