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

[juan_gandhi]

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

Comments

[spamsink.livejournal.com]

Не скажи. Если сравнение дорогое, то лучше так, чем insertion sort.

[os80.livejournal.com]

Ха! Где сравнение дорогое ("в жизни"), там ещё есть ошибки эксперимента и т.п., а элегантные решения к таким вещам часто гораздо менее устойчивы, чем "тупые".

[spamsink.livejournal.com]

Я не про жизнь, а про объекты со сложной структурой. Да хотя бы точки в пространстве, которые нужно сортировать по расстоянию от чего-либо.

[os80.livejournal.com]

Я что-то не понимаю? Ведь для точек, я так понял, самая "тяжёлая" операция - это подсчёт расстояния, и это надо в любом случае выполнить для каждой точки по разу. А само сравнение недорогое.

[spamsink.livejournal.com]

Это я отвлекся. Возьмем лексикографическое упорядочение точек в многомерном пространстве.

[os80.livejournal.com]

Я такого термина не знаю, но если Вы имеете в виду это (http://slovari.yandex.ru/dict/lopatnikov/article/lop/lop-0674.htm), то его, кажется, можно отсортировать за n-1 сравнений, то есть имеем хорошо масштабируемое (хотя и извратное) решение. В отличие от...

[spamsink.livejournal.com]

Его - это кого?

За одно сравнение считается операция на двух сравниваемых объектах, независимо от того, как она устроена внутри.

[os80.livejournal.com]

Его - это конечное множество объектов, допускающее лексикографическое упорядочение.
За одно сравнение считается операция, равная по времени (с точностью до постоянного множителя) сравнению двух объектов.
Ну, то есть, можно подобрать такие примеры, когда время будет пропорционально O(N²). Хотя в ряде случаев O(N) можно гарантировать. Но даже в самом худшем случае результат будет не хуже альтернативных способов, не учитывающих особенностей процедуры сравнения. И чем "дороже" единичная операция сравнения, тем больше будет выигрыш.

[spamsink.livejournal.com]

"Подобрать примеры" неинтересно. Интересно среднее (или ожидаемое) количество сравнений по всем возможным перестановкам.

[malaya-zemlya.livejournal.com]

merge sort всего на 1 сравнение хуже оптимального (а то не всегда), зато гораздо понятнее.

[spamsink.livejournal.com]

зато гораздо понятнее

Как там классики писали?

/* you're not supposed to understand this */