Задача сортировки — это классическая задача, которую должен знать любой программист. Именно поэтому эта статья посвящена данной теме — реализации сортировки на платформе .NET. Я хочу рассказать о том, как устроена сортировка массивов в .NET, поговорить о ее особенностях, реализации, а также провести небольшое сравнение с Java.

Итак, начнем с того, что первые версии .NET используют алгоритм быстрой сортировки по умолчанию. Поэтому небольшой экскурс в быструю сортировку:

Недавно на хабре в очередной подняли тему алгоритмов сортировки, а именно был хорошо описан метод Timsort.

Он, имея сложность не более O(n log n), ускоряется в случае сортировки частично упорядоченных данных и имеет сложность O(n), если данные изначально отсортированны. Но это не единственный алгоритм с такими заявленными свойствами. Существует еще как минимум два более-менее известных метода с похожей сложностью — это Smoothsort и сортировка Шелла.

Но то, что они имеют похожую сложность, совсем не значит, что все они работают одинаково быстро. Я попытался сравнить их реальную скорость работы на разных данных и посмотреть кто лучше справляется со своей задачей.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

Интерфейс CS-Playground-React

Я программист-самоучка. Это значит, что я постоянно имею дело с синдромом самозванца. Для меня не редкость чувствовать, что я неполноценный, и я в невыгодном положении для понимания сложных концепций информатики.

Я никогда не разбирался в математике. И я всегда привязывал сильные математические навыки к своей естественной способности преуспеть в программировании. Я чувствую, что мне приходится больше работать, чем другим (у которых есть врожденные навыки к математике), чтобы изучать одни и те же понятия. С этой идеей, глубоко укоренившейся в моем мозгу, я был уверен, что никогда не смогу научиться чему-либо, например, обходить деревья двоичного поиска, и как мысленно анализировать рекурсивные кошмары, такие как сортировка слиянием.

Зайдите на CS-Playground-React, простую браузерную JavaScript-песочницу для изучения и практикования алгоритмов и структур данных.

Это приложение не требует регистрации и автоматически сохраняет ваши достижения, предлагает решения когда вы застряли, и имеет кучу ссылок на полезные статьи, туториалы, и другие ресурсы, чтобы помочь сделать ваше обучение не очень болезненным, как было у меня.

Если вы не изучали JavaScript с самого начала, то осваивать его современную версию сложно. Экосистема быстро растёт и меняется, так что трудно разобраться с проблемами, для решения которых придуманы разные инструменты. Я начал программировать в 1998-м, но начал понимать JavaScript только в 2014-м. Помню, как просматривал Browserify и смотрел на его слоган:

Browserify позволяет делать require («модули») в браузере, объединяя все ваши зависимости

Я не понял ни слова из предложения и стал разбираться, как это может помочь мне как разработчику.

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

Ольга Базалева, создатель Data Vis и автор блога, написала статью специально для Нетологии о самых важных принципах визуализации. Статья участвует в конкурсе блога.

Хотите выделяться на фоне конкурентов? Чтобы ваши статьи, отчеты, презентации или посты в социальных сетях были профессиональными, интересными и доступными широкой аудитории? Используйте визуализацию данных!

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



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

Вступление

На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.

От переводчика. Перевод статьи 2011 года на arxiv.org о статистическом анализе модификации быстрой сортировки. Наверняка найдутся люди, использующие описанный вариант интуитивно. Здесь — математическое обоснование эффективности при n <= 7 000 000

Введение

Ключевые слова
Внутренняя сортировка; Равномерное распределение; Средняя временная сложность; Статистический анализ; Статистическая оценка

Забавной находкой поделился сегодня пользователь fj333 с Reddit. Разбираясь в появившемся год назад проприетарном коде Qualcomm Technologies для Android, он обнаружил, что неизвестный программист решил в production-коде использовать сортировку пузырьком для того, чтобы найти… максимум в массиве.

Посмотреть исходный файл вы сможете по ссылке на Github или же под катом, а оценить его в работе может любой владелец устройства с Qualcomm Snapdragon 200 MSM8610 под управлением Android.

Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде обычно не применяющийся в силу своей неэффективности; дело в том, что в наихудшем и среднем случаях он имеет сложность О(n²), к тому же его емкостная сложность в данном случае — O(n). Кого это не убедило — использовать сортировку пузырьком не рекомендует даже Барак Обама.

И это всё не учитывая того, что для поиска максимума хватило бы и простого перебора.

Так вышло, что для получение автомата по программированию бедным первокурам задали одну интересную задачу: написать программу, которая ищет по дереву методом Монте-Карло.

«Крестики-нолики» — игра изученная вдоль и поперек, и разработка ИИ для неё может свестись к организации дерева решений описанного в Википедии. В данной статье будет рассмотрено решение игры с помощью обучения с подкреплением и аппроксимацией функций ценности.

Алгоритмы — это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую философию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время?

Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы — это просто. А грокать алгоритмы — это веселое и увлекательное занятие.

Всем привет! Сегодня речь пойдет о не самом известном алгоритме сортировки — трехпутевая поразрядная быстрая сортировка. Этот алгоритм является гибридом широко известных быстрой сортировки и поразрядной сортировки.

Подробности — под катом.

Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.

Есть много примеров того, как Хаскель делает простые проблемы сложными. Вероятно, самый известный из них—это решето Эратосфена, которое легко написать на любом императивном языке, но настолько сложно написать на Хаскеле, что почти все решения, которые преподавались в университетах и использовались в исследованиях последние 18 лет, оказались неправильными. На их несостоятельность обратила внимание Мелисса О'Нил [Melissa O'Neill] в своей важной научной работе "Настоящее решето Эратосфена". В ней приводится прекрасное описание того, что не так в старых подходах, и как их надо исправить. Решением Мелиссы было использовать очередь с приоритетом [priority queue] для реализации решета. Правильное решение оказалось в 10 раз длиннее, чем намного более простое решение на F# и в целых 100 раз длиннее, чем оригинальный изуродованный алгоритм на Хаскеле.

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

Я хотел бы сказать большое спасибо А. Дайняк за прочитанный курс и добавить, что это лишь изложение кусочка курса, и на большее я не претендую.

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

Поэтому возникла идея написать собственный механизм простого тестирования скорости различных операций. Задумка показалась интересной, поэтому начало было положено!

Введение

В этой заметке я хочу рассказать о том, как можно достаточно легко строить интерактивные графики в Jupyter Notebook'e с помощью библиотеки plotly. Более того, для их построения не нужно поднимать свой сервер и писать код на javascript. Еще один большой плюс предлагаемого подхода — визуализации будут работать и в NBViewer'e, т.е. можно будет легко поделиться своими результатами с коллегами. Вот, например, мой код для этой заметки.

Для примеров я взяла скаченные в апреле данные о фильмах (год выпуска, оценки на КиноПоиске и IMDb, жанры и т.д.). Я выгрузила данные по всем фильмам, у которых было хотя бы 100 оценок — всего 36417 фильмов. Про то, как скачать и распарсить данные КиноПоиска, я рассказывала в предыдущем посте.

Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована». Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был. Первые попытки составить алгоритм сортировки очереди приводили к вопросу о том, как выйти из бесконечного цикла, но в конечном итоге я получил необходимый алгоритм, о котором и пойдёт речь.

Привет всем!

У меня есть одно хобби – я очень люблю изобретать велосипеды.
Об изобретении одного такого велосипеда хочу вам сегодня рассказать.

Сортировка массива данных – задача, которой далеко уже не первый год. Она преследует нас с первых курсов технических вузов, а кому особенно повезло, то и со школьной скамьи. Обычно это методы сортировки “пузырьком”, “делением”, “быстрая”, “вставками” и прочие.


Вот, к примеру, подобной реализации метода сортировки “пузырьком” меня учили в одной крупной IT-компании. Этот метод использовался матёрыми программистами там повсеместно.

Так вот, мне всегда было интересно, почему уделяется так мало внимания методам сортировки без сравнения (поразрядная, блочная и т.п.). Ведь подобные методы относятся к классу быстрых алгоритмов, выполняются за О(N) количество чтений и перестановок и при удачно подобранных данных могут выполняться за линейное время.

Привет, Хаброжители! У нас вышла новинка:

Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.

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

Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математи-чески чистого ядра задачи и выявления методов проектирования подходящего алгоритма на осно-вании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быст-рее он начинает распознавать «чистые» формулировки, лежащие в основе запутанных задач реального мира.