Метод сортировки FlashSort

[pkalinin]

У обобщенной сортировки теоретическое ограничение — N*log(N) сравнений. А вот перестановок, как верно заметили ниже — получить O(N) нет никаких проблем, поэтому заголовок не претенциозный, а скорее наоборот.

[denisskin]

угу. не учел. заголовок получился весьма тривиальный.
количество перестановок – О(N)
количество чтений тоже – O(N) (сравнений как таковых тут нет)
памяти О(1)

можно было бы написать Метод сортировки за линейное время )) но увы, это не всегда так.

[chersanya]

количество перестановок – О(N)
количество чтений тоже – O(N)
памяти О(1)

можно было бы написать Метод сортировки за линейное время )) но увы, это не всегда так.

Если сортировка не всегда за линейное время, то какие операции дают это самое бОльшее время?

[chersanya]

Сортировку за O(N) перестановок объектов сделать проще некуда: ищем минимальный элемент, меняем его с первым в массиве — вот и свели задачу к задаче на единицу меньшего размера за одну перестановку, соответственно перестановок всего будет не более N. Сравнений да, квадратичное количество.
Поэтому лучше уточнить, что вы имеете в виду под перестановками в тексте.

[RidgeA]

ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8

[Ivan22]

Я не совсем понял — количество buckets всегда равно количеству элементов?

[denisskin]

нет. оно всегда равно 256

[valemak]

Красивое название FlashSort, увы, уже занято. Оно закрепилось за алгоритмом, который предложил Карл-Дитрих нойберт в 1998 году. Тоже из класса сортировок распределением, однако общий принцип действия там другой. Писал как-то статейку про неё.

Ваши идеи напомнили мне сортировку "Американский флаг".

[denisskin]

Честно говоря, не гуглил когда называл. Надо было хоть как-то назвать. Вот и решил назвать примерно также пафосно как quick-sort -)

[denisskin]

за ссылку спасибо! до этого даже не знал про такой метод

[andrew-tifon]

Благодаря таким 'изобретателям велосипедов' прогресс и двигается. Спасибо за статью

[Gryphon88]

А не подскажете, есть ли где-то большой список алгоритмов сортировки с указанием, какой на каких данных себя лучше ведёт?

[denisskin]

не могу точно сказать. не знаю.

знаю одну отличную либу на Си от tony2001, которая реализует и бенчит разные методы сортировки:
github.com/tony2001/sort

[Irker]

Есть например вот такой сайт: http://www.sorting-algorithms.com/. Вероятно это не то, что вам нужно, но мне кажется он интересен.

[Gryphon88]

Спасибо, очень наглядно, но немного не то: хотелось бы много разных алгоритмов. Ссылка denisskin ближе к моим желаниям :)

[And3en]

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

[denisskin]

эмм… а мне казалось, в «стандартной» имплементации и реализован стандартный алгоритм. там просто вместо «классического» рекурсивного вызова организован собственный стек вызовов и добавлено исключение для случая, когда элементов меньше 7. реализация с рекурсивным вызовом функции, уверен, будет работать медленнее, особенно с ростом количества данных.
но Вы безусловно правы в том что необходимо сравнивать с другими методами сортировки, плюс на различных типах данных.

[veontomo]

Не могли бы вы пояснить, что означает «переставляем элементы в исходном массиве таким образом, чтобы каждый из них оказался на своем месте, в своем кармане»? Что значит, что элемент находится «в своем кармане»?

[Ivan22]

Я так понял — у нас корзина на 256 карманов, карманы уже отсортированы. Если элемент попал в 1-й карман, то он и физически должен быть первым — его надо переставить на первую позицию. Там рисунки очень хорошие

[mbezoyan]

А в чем отличие от radix sort?

[denisskin]

Да – принцип очень похож (как и во всех поразрядных сортировках).
Данный алгоритм – это скорее конкретная реализация. Есть, однако, и принципиальные отличия. Например, в radix дополнительно используется output-массив, равный по длине исходному массиву. т.е. алгоритм отъедает О(N) памяти. У нас же используется только исходный массив и перестановка элементов происходит по-месту (in-place).

Для radix sort явно не указано, как сортировать данные внутри каждой корзины.

В текущей реализации есть еще одна особенность – запоминается первый и последний номер корзины, для последующей расстановки границ корзин.

[mbezoyan]

https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations — разве не то, что надо?

[denisskin]

да. все верно, черт возьми! очень похоже на то.

[denisskin]

ок… есть еще кое-какие идеи для улучшения этой имплементации…

[DeuterideLitium6]

Интересный алгоритм. Я тоже придумал свой, ещё 20 лет назад, а недавно таки руки дошли его реализовать, и он очень похож на ваш. Так же посчитывает буквы, т.е. байты, а потом суммирует и вычисляет начальные индексы для каждой группы букв, т.е значения байта. И по этим индексам распихиваем строки, у меня используется массив bool'ов, чтобы обозначать элементы которые на своих местах. А потом рекурсивно в цикле повторяем с следующими буквами, т.е. байтами. По байтам самое удобно работать, но если у нас UTF-8, то тут надо думать, может контейнер использовать в место простого массива, короче корзины не в массиве, а в стеке например.

Кстати, написал на ассемблере UASM, но переписать на простые С++, не проблема, F5 в IDAPro и немного обработать напильником.

ЗЫ

И ещё, у меня файл leipzig1M.txt размер 123 МБ, кол. строк 1000000, мой ПК отсортировал за 0.8 сек, а ноутбук за 2.5 сек. ПК Райзен 5 3600Х, а ноутбук T4300,DDR2-800 4GB.

А файлы.

SortFile data\hashes-base64.txt
SortFile data\hashes-hex.txt
SortFile data\ip-addresses-as-nums.txt
SortFile data\numbers.txt
SortFile data\numbers-rsorted.txt
SortFile data\numbers-sorted.txt
SortFile data\words-en.txt

Мой ПК за 47, 47, 131, 156, 78, 125, 78 мс соответственно.