• J-сортировка


      Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

      С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

      Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

      Так ещё метод и прост до безобразия
    • Корректный YML для Яндекс.Маркета. Взгляд программиста


        Многие интернет-магазины попадают в Яндекс.Маркет, не все там остаются надолго. Одно из условий присутствия в ЯМ-е – наличие корректного прайса в специальном формате YML.

        Проверка такого прайса на ошибки и устранение таковых – целая история. Пока он не будет сформирован по всем правилам – вход в сие царство демпинга заказан. А при доведении документа до ума можно пережить немало незабываемых эмоций.

        Данная статья – попытка обобщить те ошибки, с которыми сталкиваются программисты, впервые создающие инструменты (будь то автономный скрипт или плагин для CMS) для генерации YML-файла. Тем, кто с этим чудным форматом имел дело раньше, статья уже будет не столь интересна, ибо всё шишки набиты. Впрочем, вдруг и ветераны борьбы за своё место под солнцем Яндекса узнают что-то новое для себя. А то и поделятся собственным фронтовым опытом.
        YML? Легко!
      • Эзотерические сортировки Дэвида Морган-Мара



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

          Сплошная алгоритмическая эзотерика
        • Глупая сортировка и некоторые другие, поумнее


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

            Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.

            image: эволюция

            Другое ответвление глупой сортировки
          • Пузырьковая сортировка и все-все-все


              Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

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

              image: пузырьки

              Сделать первый шаг в изучении сортировок
            • ABC-сортировка


                Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Впрочем, алгоритм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик (Allen Beechick) выбрал название в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.

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

                Что касается алгоритма, то это единственно известная мне сортировка, за использование которой её изобретатель требует деньги.
                Богоугодная сортировка за 88 у.е.
              • Бисерная сортировка (Bead sort)


                  Сегодня предложу Вашему вниманию симпатичный алгоритм, который хоть и придумали совсем недавно (11 лет назад), но «прототипом» послужило счётное устройство с трёхтысячелетней историей.
                  Но обо всём по порядку
                • Непрактичные сортировки – бессмысленные и беспощадные

                    image

                    А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?

                    Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.

                    Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.
                    Начнём
                  • Ещё одна сортировка распределением


                    Когда речь заходит об эффективных алгоритмах сортировок, эрудированный хабраюзер сразу же припомнит неувядаемую «быструю сортировку», новомодную «сортировку Тима», легендарную «сортировку слиянием» и даже мудрёную «интроспективную сортировку».

                    Не подвергая сомнению эффективность вышеприведённых методов, предлагаю Вашему вниманию сортировку, которая при определённых входных условиях легко уделывает по скорости любой другой алгоритм.
                    О чём, собственно, речь?