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

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

Введение

Алгоритм четно-нечетной сортировки слиянием (odd-even mergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Лично я узнал о нем когда разбирался с MPI и увидел тестовое задание на coursera: написать сортировку Бэтчера.

Всем доброго времени суток!

В этом небольшом посте я продолжу тему, которую поднимал в своих старых двух постах
Часть 1
Часть 2

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

Так что добро пожаловать под хабракат

Чего мы хотели

Есть у нас на факультете инноваций и высоких технологий МФТИ такой типа крутой курс — инновационный практикум. Если кратко — из студентов третьекурсников набираются команды, которые пытаются сделать что-то реальное, желательно связанное как-то с программированием и собственно современными технологиями. Вот этого мы и хотели добиться. Наш проект — сделать самолет(да, не нынче модные квадрокоптеры!), который будет уметь взлетать/садиться в автоматическом режиме, летать по точкам GPS, и снимать все, что видит, на встроенную камеру. FPV мы тоже хотели, но попозже.

Ремарка

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

В продолжение к моей первой статье решил написать эту, в которой расскажу про более продвинутые алгоритмы поиска гамильтонова цикла в большом полном графе

Про дерево Фенвика многие знают. Многие его используют. Однако считается, что деревом Фенвика нельзя находить максимум/минимум.
Мол, эта операция не имеет обратной. Однако небольшие изменения алгоритма позволяют нам решить и эту задачу тоже.
NB: Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.Тем, кто не знает, что такое дерево Фенвика, рекомендуется прочитать об этом где-нибудь, хоть в Кормене, хоть в статье на хабре.

1. Постановка задачи

Полный взвешенный граф из 500 вершин задан матрицей смежности.
Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.