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

Сортировка «Ханойская башня» - 1

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.) Читать полностью »

Поняв, как работать с электромеханическим сортировщиком перфокарт (с точки зрения обычного пользователя), и приступая к более тесному знакомству с ним (с точки зрения инженера), – ожидаешь увидеть в нём несколько датчиков для считывания отверстий в перфокартах и с десяток манипуляторов, каждый из которых забирает перфокарту в свой карман. Однако электромеханика сортировщика намного более элегантна и проста: весь его интеллект держится на одном датчике и на одном электромагните. Как именно, читайте ниже.

Тесное знакомство с электромеханическим сортировщиком перфокарт (экскурс в начало XX века) - 1

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

В период 1890-1970 вся обработка больших данных осуществлялась через перфокарты. Перфокарты в свою очередь обрабатывались при помощи т.н. «регистрирующей аппаратурой», центральным звеном которой был электромеханический «сортировщик перфокарт». Перфокарты и сопутствующую аппаратуру применяли для решения самых разнообразных задач: перепись населения, бухгалтерский учёт, инвентаризация, расчёт заработной платы и т.д.

Как люди работали с перфокартами? Какому алгоритму следовал электромеханический сортировщик перфокарт? Как осуществлялась сортировка по числовым полям данных? А по строковым? Обо всём этом – ниже.

Ликбез по работе с перфокартами (или история о том, как с 1890-го по 1970-й «большие данные» обрабатывались) - 1

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

Обнаружен универсальный метод сортировки сложной информации - 1

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

Это пример задачи поиска "ближайшего соседа", которую широко изучают в информатике. Дан набор сведений и новая точка, и требуется найти, к какой точке из уже существующих она окажется ближайшей? Такой вопрос возникает во множестве повседневных ситуаций в таких областях, как исследование генома, поиск картинок и рекомендации на Spotify.

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

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

Мои любимые примеры функционального программирования в языке Kotlin

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

Экзамен в школе прапорщиков.
— Вот смотрите. Это большой палец, это — указательный, это — средний, это — безымянный, это — мизинец. Мешаем, мешаем, мешаем (двигает пальцами)… Теперь где какой?

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

Перед моими студентами регулярно встаёт задача случайного перемешивания массива. За её решением они, как правило, лезут в гугл. И гугл им подсказывает следующее:

var shuffledArr = arr.sort(function{
  return Math.random() - 0.5;
});

Сегодня я решил написать о том, какие преимущества и недостатки есть у такого подхода.
Читать полностью »

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

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

imageДанная статья является продолжением моей статьи "Python: коллекции, часть 1: классификация, общие подходы и методы, конвертация".

В данной статье мы продолжим изучать общие принципы работы со стандартными коллекциями (модуль collections в ней не рассматривается) Python.

Для кого: для изучающих Python и уже имеющих начальное представление о коллекциях и работе с ними, желающих систематизировать и углубить свои знания, сложить их в целостную картину.
Читать полностью »

Всем привет!

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

Этот алгоритм является гибридом широко известных быстрой сортировки и поразрядной сортировки.

Подробности — под катом.
Читать полностью »

Привет! Недавно пришло интересное задание:

Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.

Самым ленивым способом отсортировать можно используя «внешнюю сортировку со слиянием», но это весьма тяжёлый и долгий метод. В этой публикации я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.
Читать полностью »