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

Здравствуйте, hpux100

Да — применяются... во всех.. Но долбапрограммистов, реализующих их врукопашную своими силами под каждый новый проект, к счастью, все меньше и меньше... Иногда (ну в очень редких случаях) требуется понимать какой из алгоритмов дает выигрыш и в ущерб чему (ну это не только к "сортировкам" относится)... На собеседованиях же, даже исходя из названия сего мероприятия, отбирают собеседников... Вот пойдете Вы с "пацанами" (или как там будут называть коллеги друг друга?) пива выпить после работы... Ну не о бабах девушках или тачках автомобилях ну и другом житейском шлаке трындеть... А так о малое, о-по большому... омега с логарифмами... и уважение к собеседнику растет... Как-то так...

Здравствуйте, hpux100, Вы писали:

H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

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

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, hpux100, Вы писали:

H>>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

RO>Вручную реализовывать почти никогда не нужно, а вот теорию знать очень полезно. Например, устойчивость/неустойчивость, или какие ограничения накладываются на предикаты, или что делать, если массив очень велик, но разных значений там мало, или как работать с уже упорядоченным массивом.

я не про ручную в том числе, понимание того как это работает да, важно, интересны примеры где в промышленных проектах и для чего используется например std::sort

Здравствуйте, hpux100, Вы писали:


H>я не про ручную в том числе, понимание того как это работает да, важно, интересны примеры где в промышленных проектах и для чего используется например std::sort

да хотябы в листбокс вывести список отсортированный по алфавиту,
или отсортировать для ускорения поиска ...

Здравствуйте, hpux100, Вы писали:

H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.
Я целый раз применял! Более того, даже пузырек написал сам лично . По причине, что писал на VB Script, и там со стандартными средствами беда была.
А так — иногда случается хитрая бизнес логика, когда нужно для получения результата отсортировать по определенному ключу.

Здравствуйте, hpux100, Вы писали:

H>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.
не совсем сортировка, но в тему школьных алгоритмов.

давным-давно понадобилось написать аналог Shadow Copy для одной альтернативной операционки — драйвер, который позволял "заморозить" состояние диска в некий момент и постепенно его считать в архив (реализовывалось отслеживанием секторов, измененных после создания снапшота, запоминанием их предыдущего состояния и подстановкой его при создании архива).

стандартных вещей вроде STL там не было, да и требования к памяти в kernel-mode довольно критичны. понимание того, чем дерево отличается от списка или хэш-таблицы помогло сделать красивое и шустро работающее решение.

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

Здравствуйте, hpux100, Вы писали:

H>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

Radix sort с плавающей точкой для определения столкновений.
реализация BWT это одна сплошная хардкорная сортировка.
в computational geometry свои версии сортировок для растеризации . операциями над полигонами и т.п.
Сортировки для данных с известным распределением (частично отсортированные, равномерно распределенные на численном интервале).

это навскидку.

Здравствуйте, hpux100, Вы писали:

H>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

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

Реально на практике такое писать придется только если пишешь свой собсвенный велосипед фреймворк или пишешь в среде в которой еще не ступала нога фреймворкиста. В бизнес проекте за это сразу получишь по шее от сеньера.

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

Хотя конечно, если нужен real time performance, существующие алгортмы не справляются и специфика очень узконаправленная, значит пришло время повеселится и заняться тем, чем мы так мечтаем заниматься когда долго засиживаемся над рутинными задачками. Да здраствует R&D.

Здравствуйте, carpenter, Вы писали:

H>>я не про ручную в том числе, понимание того как это работает да, важно, интересны примеры где в промышленных проектах и для чего используется например std::sort

C>да хотябы в листбокс вывести список отсортированный по алфавиту,
C>или отсортировать для ускорения поиска ...

для этого надо использовать какойнить sorted_container, а не std::sort

Здравствуйте, hpux100, Вы писали:

H>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

алгоритмы сжатия — это сплошь самодельные лисапеды на тему поиска информации.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>алгоритмы сжатия — это сплошь самодельные лисапеды на тему поиска информации.

На вопрос "где применяются алгоритмы сжатия" ответить не легче.

Здравствуйте, hpux100, Вы писали:

H>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

В моем случае была не сортировка, а поиск. Архитектор системы с большим практическим опытом, который так ценят местные форумчане, не учел вычислительную сложность поиска и при большом числе объектов получилась лажа. Пока объектов были сотни-тысячи (тестовая среда) все было ок, но в реальной жизни их сотни тысяч и все сильно тормозит.

Клепателям форм сортировка не столь актуальна конечно.

Здравствуйте, hpux100, Вы писали:

Зачем учить алгоритмы, если достаточно написать order by ?

Здравствуйте, carpenter, Вы писали:

H>>я не про ручную в том числе, понимание того как это работает да, важно, интересны примеры где в промышленных проектах и для чего используется например std::sort
C>да хотябы в листбокс вывести список отсортированный по алфавиту,
C>или отсортировать для ускорения поиска ...

Дык в венде ж стиль для этого специальный в списковых контролах уже есть (LBS_SORT/CBS_SORT). Неуж-то на каких-то платформах нет?

Здравствуйте, hpux100, Вы писали:

H>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

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

Здравствуйте, hpux100, Вы писали:

H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.

По моему опыту так: основная масса (90%) сложных алгоритмов никогда не разрабатывают (не, ну в книжке вычитать и запомнить могут, но не более того). А зачем, если алгоритм нужно разработать (и выразить на том или ином языке) лишь 1 раз и использовать потом смогут все?

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

Здравствуйте, _FRED_, Вы писали:

_FR>В VB 6 стандартная библиотека была настолько убога, что бинарный поиск вот приходилось писать самим. Так же, если было нужно отсортировать набор чего-то по какому-либо условию — засучивай рукава.

А что там засучивать: находишь на github готовую реализацию на любимом языке программирования и меняешь названия функций. Все! Даже не нужно понимать как оно работает.

Здравствуйте, minorlogic, Вы писали:

M>Здравствуйте, hpux100, Вы писали:

H>>На собеседовании часто задают вопрос по алгоритмам сортировок.
H>>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
H>>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.

M>Radix sort с плавающей точкой для определения столкновений.
M>реализация BWT это одна сплошная хардкорная сортировка.
M>в computational geometry свои версии сортировок для растеризации . операциями над полигонами и т.п.
M>Сортировки для данных с известным распределением (частично отсортированные, равномерно распределенные на численном интервале).

Добавлю из своего опыта.
В САПР сплошь и рядом.

Самое элементарное:
Проверка попадания мышкой в графическом редакторе.

Из посложнее:
Восстановление электрических связей по геометрическим данным.
Сборка padstack'ов из разрозненных деталей.
Поиск правил (constraints), действующих между двумя заданными объектами.
Проверка конструкторско-технологических ограничений.

Хардкор:
автотрассировка, авторазмещение.

Тут тебе и простые хеши, и 2D-хеши, и различные сортировки. Где-то достаточно std::sort, где-то — пирамидальная. Даже развороту односвязного списка находится место.

On 16.02.2013 21:52, Roman Odaisky wrote:

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