Рубрика «сортировки»

Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.

Лекция 1. Основы

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


Читать полностью »

Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:

  1. Время выполнения — гарантированные O(nlogn).
  2. Использование O(1) дополнительной памяти.
  3. Применимость для сортировки данных в односвязных списках.

Оговорки на все три ограничения:

  1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
  2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
  3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку).

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

Под катом можно узнать, что в итоге получилось у нас.

Challenge. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.

Читать полностью »

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

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

image: эволюция

Читать полностью »

image

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

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

Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.
Читать полностью »

Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу Читать полностью »

В прошлых статьях я затрагивал тему простых рейтингов. В комментариях меня попросили расписать тему рейтингов, которые выдают для каждого пользователя свои.
Читать полностью »

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

Прошлая статья привлекла большой интерес. И даже, на некоторое время, стала лучшей за 24 часа. У меня появилось несколько идей и на часть вопросов в комментариях нужно ответить более развернуто.
image

Читать полностью »

Написать этот пост меня привлекла эта статья. Многие ее помнят по вот этой картинке.
image
Статья затрагивает правильную тему, однако с точки зрения математики и здравого смысла она в корне не верна.
Читать полностью »