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

[juan_gandhi]

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

Comments

[spamsink.livejournal.com]

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

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

[os80.livejournal.com]

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

[spamsink.livejournal.com]

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