Pull to refresh

Быстрая сортировка таблиц посредством Javascript

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

  • Сортировка на стороне сервера посредством SQL или backend'а;
  • Сортировка на стороне клиента.

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

Минусы сортировки на стороне клиента — сравнительно низкая скорость работы, прямо зависящая от браузера и мощности компьютера пользователя. Плюсы — отсутствие перезагрузки страницы, следовательно, иногда это дает бОльшую скорость получения отсортированного содержимого, т.к. в данном случае нет задержки между отправкой запроса серверу и получением результата.
Читать дальше →
Total votes 55: ↑44 and ↓11 +33
Views 15K
Comments 84

Олимпиадное хобби. Разделяй и властвуй

Sport programming *
Доброго всем понедельника. Если понедельник для вас не самый приятный день, то предлагаю вам немного расслабиться и проникнуться моим хобби. Моё хобби — решение олимпиадных задач по программированию: встряхивает мозг, будоражит воображение и заряжает энергией (правда не всегда положительной). Не верите? Попробуйте сами, только честно попытайтесь решить поставленную задачу, получите долгожданный Accepted, и наслаждайтесь полученными эмоциями.

Сегодня случай подкинул нам задачу №10474. Это задача на умение применять вовремя простые алгоритмы, поэтому не ждите от нее чего-то сложного и хитроумного. Если вам не интересно решать задачи за счет пары стандартных алгоритмов, то пропускайте топик, а всем остальным добро пожаловать под кат. Нас ждет пара алгоритмов, выбор наиболее удобного решения, ну и, конечно же, Accepted!
Читать дальше →
Total votes 28: ↑23 and ↓5 +18
Views 5.6K
Comments 36

Интересное поведение сортировки в .NET

.NET *
Sandbox
Всё началось с того, что на работе у коллеги стали падать тесты. Причём только у неё одной. Вдаваться в подробности не буду, но суть в том, что в тесте было два объекта List. Первый был эталонным, а второй — возвращался тестируемым методом. Затем листы сравнивались поэлементно.
Очень быстро было выяснена причина падения теста: у коллеги порядок элементов в результирующем массиве был обратным порядку в эталонном массиве. В коде тестируемого метода использовался стандартный List.Sort с нашим компаратором, который именно на этом тесте всегда возвращает 0. Но у всей команды элементы возвращались в одном порядке, а у одной сотрудницы — строго в обратном. Было быстро выяснено, что у коллеги давно не было обновлений и версия mscorlib.dll у неё сильно отличалась от той, что была у остальных. На этом можно было бы и успокоиться, но мне стало интересно я решил копать дальше и вот что выяснил.
Читать дальше →
Total votes 29: ↑15 and ↓14 +1
Views 5K
Comments 21

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

Perfect code *C++ *Algorithms *

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

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

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

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

Perfect code *Algorithms *

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

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

image: пузырьки

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

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

Perfect code *Algorithms *

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

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

image: эволюция

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

Визуализация алгоритмов

Algorithms *Data visualization
Специалист по дата-майнингу и визуализации данных Майк Босток (Mike Bostock) опубликовал великолепную подборку с визуализацией различных алгоритмов.

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

Проще говоря, зрение помогает нам думать.
Читать дальше →
Total votes 49: ↑42 and ↓7 +35
Views 35K
Comments 8

Реализация сортировки в V8 от Google

JavaScript *Algorithms *Node.JS *
image
Привет, Хабр.

Мир javascript развивается с невероятной скоростью: новые стандарты языка, новые фреймворки, и в браузере, и на сервере и в десктопных приложениях и так далее… Но иногда хочется вместо изучения новой супер-фичи погрузиться в какую-то более базовую тему. И погрузиться глубоко, до самых исходников.

И в этот момент под моим пристальным взглядом оказалась незаметная строчка «native code», которая так или иначе появляется перед глазами любого JS разработчика в консоли Chrome или Node.js:

[].sort.toString();
"function sort() { [native code] }"

Итак, кому интересно, какая реализация сортировки скрывается в V8 за надписью [native code] — добро пожаловать под кат.
Читать дальше →
Total votes 58: ↑57 and ↓1 +56
Views 36K
Comments 8

Трехпутевая поразрядная быстрая сортировка

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

Подробности — под катом.
Читать дальше →
Total votes 24: ↑24 and ↓0 +24
Views 18K
Comments 18

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

C++ *Algorithms *Visual Studio *
Sandbox
В данной статье рассматриваются алгоритмы сортировки массивов. Для начала представляются выбранные для тестирования алгоритмы с кратким описанием их работы, после чего производится непосредственно тестирование, результаты которого заносятся в таблицу и производятся окончательные выводы.

Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).

В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.
Читать дальше →
Total votes 37: ↑4 and ↓33 -29
Views 132K
Comments 25

Описание алгоритмов сортировки и сравнение их производительности

C++ *Algorithms *
Sandbox

Вступление


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

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать дальше →
Total votes 80: ↑76 and ↓4 +72
Views 476K
Comments 55

Самый полный русскоязычный перевод Гарвардского курса по программированию CS50 2015, бесплатно на YouTube

Programming *
Sandbox
В этой статье я хочу немного рассказать о самом лучшем в мире курсе по программированию.

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

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

image
Total votes 19: ↑18 and ↓1 +17
Views 52K
Comments 27

И ещё о сортировках

Programming *C++ *Algorithms *Processing *

И ещё о сортировках


Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать дальше →
Total votes 25: ↑23 and ↓2 +21
Views 19K
Comments 53

Сортировка выбором минимумов (максимумов)

Abnormal programming *Programming *C++ *Algorithms *
Sandbox

imageМногие программисты думают, что Quick Sort — самый быстрый алгоритм из всех существующих. Отчасти это так. Но работает она действительно хорошо только если правильно выбран опорный элемент (тогда сложность составляет O (n log n)). В противном же случае асимптотика будет примерно такой же как и у пузырика (то-есть O (n2)).
При этом, если массив уже отсортирован, то алгоритм всё-равно будет работать не быстрее, чем O (n log n)


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

«Дело было вечером, делать было нечего», — Сергей Михалков.

Требования:


  1. Лучший случай O (n)
  2. Средний случай O (n log n)
  3. Худший случай O (n log n)
  4. В среднем быстрее быстрой сортировки


А теперь давайте обо всём по порядку


Чтобы наш алгоритм всегда работал быстро, нужно чтобы в среднем случае асимптотика была хотя бы O (n log n), а в лучшем — O (n). Все мы прекрасно знаем, что в лучшем случае сортировка вставками работает за один проход. Но в худшем ей придётся гонять по массиву столько раз, сколько в нём элементов.


Читать дальше →
Total votes 24: ↑15 and ↓9 +6
Views 21K
Comments 38

Триумфальное возвращение Ломуто

High performance *C++ *Algorithms *D *
Translation

США, Техас, Остин, клуб Continental
Воскресенье, 5 января 1987 г.


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


— Спасибо, что согласились со мной встретиться, мистер… сэр… Чарльз… Энтони Ричард… Хоар. Это большая честь для меня. Я даже не знаю, как к вам обращаться. У вас есть рыцарский титул?


— Зовите меня Тони, и, если вы позволите, я буду называть вас Нико.


На первый взгляд — обычная картина: два человека наслаждаются виски. Однако внимательному наблюдателю открываются интригующие подробности. Прежде всего — напряжение, которое можно было резать ножом.


Одетый в безупречно подогнанный костюм-тройку с нарочитой небрежностью, на какую способен только англичанин, Тони Хоар был таким же воплощением Британии, как и чашка чая. Смиренное выражение лица, с которым он попивал из своего стакана, без всяких слов выражало его мнение в споре между бурбоном и скотчем. Сидевший напротив Нико Ломуто представлял полную ему противоположность: одетый в джинсы программист, мешавший виски с колой (что для Тони было настолько возмутительно, что он сразу решил подчёркнуто это игнорировать — как резкий запах пота или оскорбительную татуировку), в состоянии некого расслабленного трепета перед гигантом информатики, с которым он только что познакомился лично.


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


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

Читать дальше →
Total votes 14: ↑13 and ↓1 +12
Views 4.8K
Comments 6

Цена естественности или как обогнать QuickSort

Algorithms *
Сортировка — такая же «вечная» тема для алгоритмистов, как любовь — для поэтов. Казалось бы, новое слово в этой области сказать трудно, а поди же ты — продолжают придумывать новые алгоритмы сортировок (TimSort...) Есть, однако, базовые факты, которые знает каждый приличный студент. Известно, к примеру, что универсальный алгоритм сортировки не может быть быстрее O(n*log(n)). Такой показатель производительности имеет знаменитая QuickSort (придуманная в 1960-м году Хоаром), а также сортировка слиянием (Фон Неймана) и пирамидальная сортировка. Что же касается элементарных алгоритмов («пузырек», «вставки», «выбор»), то их показатель существенно хуже — O(n^2). Но всегда ли QuickSort является «абсолютным чемпионом»?
Читать дальше →
Total votes 22: ↑16 and ↓6 +10
Views 5.8K
Comments 28