День добрый. Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована». Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был. Первые попытки составить алгоритм сортировки очереди приводили к вопросу о том, как выйти из бесконечного цикла, но в конечном итоге я получил необходимый алгоритм, о котором и пойдёт речь.
Читать полностью »
Рубрика «сортировка» - 4
Сортировка очереди без использования дополнительных ресурсов
2016-03-28 в 11:43, admin, рубрики: Алгоритмы, очередь, сортировка, сортировка очередиТаблицы сортировки в СУБД Caché
2016-03-25 в 15:57, admin, рубрики: cache, collation, Блог компании InterSystems, Локализация продуктов, порядок, сортировка 
Зато какая сортировка!
(А. С. Пушкин)
Если бы это была запись для твиттера, то она была бы следующей: «Программисты на Caché ObjectScript! Используйте Cyrillic4 вместо Cyrillic3!». Но тут Хабр, поэтому придётся развернуть мысль – добро пожаловать под кат.Читать полностью »
Сравнение алгоритмов сортировки
2015-12-25 в 8:20, admin, рубрики: c++, Visual Studio, алгоритм сортировки, Алгоритмы, быстрая сортировка, сортировка, сортировка вставками, сортировка массива, сортировка пузырьком, сортировка расчёскойВ данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы.
Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).
В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.
Читать полностью »
Доказательство некорректности алгоритма сортировки Android, Java и Python
2015-03-01 в 13:00, admin, рубрики: java, python, timsort, Алгоритмы, баг, Программирование, Разработка под android, сортировкаТим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.
Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.
Статья с более полным анализом, а также несколько тестовых программ доступны на нашем сайте.
Читать полностью »
Решение задач на определение фальшивой монеты взвешиванием 2.0
2014-11-17 в 20:21, admin, рубрики: Алгоритмы, сортировкаСегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.
Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.
Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.
BitSorting Алгоритм со сложностью О(n)
2014-03-11 в 12:48, admin, рубрики: O(n), Алгоритмы, сортировка, метки: сортировка .png "BitSorting Алгоритм со сложностью О(n)")
Предыстория
В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность O(n) не занимал бы много дополнительной памяти и мог бы быть легко распараллелен. И добился некоторого результата.
Читать полностью »
Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)
2013-12-29 в 20:24, admin, рубрики: Action Script, actionscript, as3, Flash-платформа, merge sort, Алгоритмы, сортировка, сортировка слиянием, метки: actionscript, as3, merge sort, сортировка, сортировка слиянием .png "Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)")
Слева — mergeSort, справа — родная сортировка. PepperFlash и 75 миллионов элементов.Читать полностью »
Быстрая, экономная, устойчивая…
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), в которой описан именно такой алгоритм.
Глупая сортировка и некоторые другие, поумнее
2013-12-05 в 15:14, admin, рубрики: Алгоритмы, быстрая сортировка, пузырьковая сортировка, Совершенный код, сортировка, сортировка вставками, сортировки, Учебный процесс в IT, метки: быстрая сортировка, пузырьковая сортировка, сортировка, сортировка вставками, сортировки 
В прошлой статье мы оттолкнулись от так называемой глупой сортировки и путём нехитрых метаморфоз получили всем известную пузырьковую сортировку. Трансформируя последнюю пришли к целому вороху обменных способов упорядочивания массивов. Один из которых, между прочим, на структурах до нескольких тысяч элементов, даже работает быстрее чем быстрая сортировка.
Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.
image: эволюция
Не все комментарии одинаково полезны
2014-01-20 в 14:08, admin, рубрики: comments, digg, Алгоритмы, комментарии, математика, Медиа, ранжирование, сортировка, хабрахабр, метки: comments, digg, комментарии, ранжирование, сортировка, ХабрахабрДостаточно много статей на хабре набирает существенное количество комментариев, e.g. в статьях "лучшее за месяц" их, как правило, более сотни. За годы чтения хабра, создалось впечатление, что примерно в половине случаев для комментариев первого уровня получается вот такая вот картина
(картинка сделана на основе хабра-статьи Список скептика)
Под катом рассказ, какие бывают сортировки комментариев, где они применяются и краткое рассуждение о том, как вообще можно сортировать комментарии (и зачем).
Читать полностью »