.png "Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)")
Слева — mergeSort, справа — родная сортировка. PepperFlash и 75 миллионов элементов.Читать полностью »
Метка «сортировка слиянием»
Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)
2013-12-29 в 20:24, admin, рубрики: Action Script, actionscript, as3, Flash-платформа, merge sort, Алгоритмы, сортировка, сортировка слиянием, метки: actionscript, as3, merge sort, сортировка, сортировка слияниемБыстрая, экономная, устойчивая…
2013-12-09 в 3:01, admin, рубрики: Алгоритмы, алгоритмы сортировки, математика, сортировка, сортировка слиянием, метки: алгоритмы сортировки, сортировка, сортировка слиянием 
Если вам понадобится алгоритм сортировки массива, который:
- Работал бы гарантированно за O(N*log(N)) операций (обменов и сравнений);
- Требовал бы O(1) дополнительной памяти;
- Был бы устойчивым (то есть, не менял порядок элементов с одинаковыми ключами)
то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N2)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)2) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().
На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)2) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан именно такой алгоритм.
Алгоритмы / Сортировка слиянием без использования дополнительной памяти
2012-02-13 в 20:37, admin, рубрики: merge, merge sort, Алгоритмы, алгоритмы сортировки, сортировка слиянием, метки: merge, merge sort, Алгоритмы, алгоритмы сортировки, сортировка слиянием Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.
Но я все-таки решил попробовать.
Слияние за линейное время
Идея алгоритма довольноЧитать полностью »