Pull to refresh
  • by relevance
  • by date
  • by rating

О сортировке контента на основе оценок пользователей

Website development *Algorithms *
Написать этот пост меня привлекла эта статья. Многие ее помнят по вот этой картинке.
image
Статья затрагивает правильную тему, однако с точки зрения математики и здравого смысла она в корне не верна.
Читать дальше →
Total votes 133: ↑117 and ↓16 +101
Views 16K
Comments 62

О сортировке контента на основе оценок пользователей: Часть 2

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

Читать дальше →
Total votes 67: ↑52 and ↓15 +37
Views 9.9K
Comments 36

О сортировке контента на основе оценок пользователей: Часть 3

Website development *Algorithms *Mathematics *
В прошлой статье я вывел формулу, которая прогнозирует рейтинг на основе оценок статьи и средней оценки по сайту. Думал в этой статье, я покажу качество ее прогноза, улучшу прогноз за счет дисперсии. Однако, появилась еще одна проблема.
image
Читать дальше →
Total votes 58: ↑44 and ↓14 +30
Views 14K
Comments 4

О создании персональных рейтингов. Вроде IMHO.net

Website development *Algorithms *Mathematics *
В прошлых статьях я затрагивал тему простых рейтингов. В комментариях меня попросили расписать тему рейтингов, которые выдают для каждого пользователя свои.
Читать дальше →
Total votes 31: ↑27 and ↓4 +23
Views 6.6K
Comments 1

Алгоритмы и структуры данных — шпаргалка

Algorithms *
Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу поделиться. Самое главное, что взял из этих слайдов, — это вышеупомянутые сводные таблички. Думаю многим пригодится.
Читать дальше →
Total votes 76: ↑61 and ↓15 +46
Views 193K
Comments 43

Непрактичные сортировки – бессмысленные и беспощадные

Abnormal programming *Java *Algorithms *
image

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

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

Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.
Начнём
Total votes 95: ↑82 and ↓13 +69
Views 80K
Comments 54

ABC-сортировка

Perfect code *C++ *Algorithms *

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

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

Что касается алгоритма, то это единственно известная мне сортировка, за использование которой её изобретатель требует деньги.
Богоугодная сортировка за 88 у.е.
Total votes 37: ↑33 and ↓4 +29
Views 40K
Comments 24

Пузырьковая сортировка и все-все-все

Perfect code *Algorithms *

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

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

image: пузырьки

Сделать первый шаг в изучении сортировок
Total votes 116: ↑104 and ↓12 +92
Views 497K
Comments 30

Глупая сортировка и некоторые другие, поумнее

Perfect code *Algorithms *

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

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

image: эволюция

Другое ответвление глупой сортировки
Total votes 69: ↑62 and ↓7 +55
Views 89K
Comments 23

Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти

Algorithms *
Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:
  1. Время выполнения — гарантированные O(nlogn).
  2. Использование O(1) дополнительной памяти.
  3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

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

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

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

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

Читать дальше →
Total votes 70: ↑67 and ↓3 +64
Views 49K
Comments 85

Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных

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

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


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


Читать дальше →
Total votes 52: ↑48 and ↓4 +44
Views 124K
Comments 14

О сортировках (пузырьковой, быстрой, расческой...)

Programming *
Recovery mode
Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все. Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту. Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.

Читать дальше →
Total votes 14: ↑5 and ↓9 -4
Views 37K
Comments 13

Сортировки слиянием

Edison corporate blog Python *Algorithms *Concurrent computing *History of IT

Сортировки слиянием работают по такому принципу:

  1. Ищутся (как вариант — формируются) упорядоченные подмассивы.
  2. Упорядоченные подмассивы соединяются в общий упорядоченный подмассив.
Траффик
Total votes 11: ↑11 and ↓0 +11
Views 17K
Comments 10

Сбалансированное слияние сверху-вниз и снизу-вверх

Edison corporate blog Programming *Algorithms *C *Concurrent computing *

В прошлой статье мы ознакомились с реликтовыми сортировками слияния (вызывающих прежде всего исторический интерес). А что в тренде сегодня?
Траффик
Total votes 15: ↑15 and ↓0 +15
Views 4.1K
Comments 0

Подсчёт с приблизительным распределением — чаще всего переизобретаемая сортировка

Edison corporate blog JavaScript *Java *Perfect code *Algorithms *

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

Чаще прочих встречается вот такая алгоритмическая идея.

Каждый элемент заносится примерно в то место массива, где он должен находиться. Получается почти упорядоченный массив. К которому или применяется сортировка вставками (она самая эффективная для обработки почти упорядоченных массивов) или локальные неупорядоченные области обрабатываются рекурсивно этим же алгоритмом.
Траффик
Total votes 21: ↑21 and ↓0 +21
Views 4.8K
Comments 2

Сортировка «Американский флаг»

Edison corporate blog Python *Perfect code *Algorithms *Data visualization

Чтобы понять принцип действия этой «многополосной» сортировки проще для начала разобраться на примере флага с тремя полосами. А чтобы легко разобраться с трёхцветным флагом, лучше сначала посмотреть, как это работает на примере двухцветного. А чтобы разобраться с двухцветным...
Траффик
Total votes 32: ↑30 and ↓2 +28
Views 13K
Comments 3

Гибридные сортировки

Edison corporate blog Programming *Perfect code *Algorithms *Data visualization


Как все уже знают, в основу сортировки могут быть положены обмены, вставки, выбор, слияние и распределение.

Но если в алгоритме комбинируются разные методы, то тогда он относится к классу гибридных сортировок.
Читать дальше →
Total votes 25: ↑25 and ↓0 +25
Views 9.3K
Comments 2
1