Цеховое: про связь науки с производством
Пару месяцев назад какая-то особенно длинная таблица стала как-то особенно медленно сортироваться. Полезли в код, а там пузырьковая сортировка с каких-то древних времен валяется. Фи, как некультурно, сказали мы и вставили стандартную сортировку Хоара (она же quick sort). И все с таблицей стало хорошо и быстро. Но вчера начали поступать жалобы с мест - что-то в некоторых других местах стало сортироваться не так, как прежде. И я, к стыду своему, не смог сообразить - какая, казалось бы, разница меж bubble и quick sort, помимо скорости?


А оказалось, что кое-кто у нас порой сортирует множества с равными элементами, а вот там-то разница есть: bubble стабильный, порядок равных элементов сохраняет, а quick переставляет их как попало.

Превращение quick sort в стабильную сортировку обошлось нам в одну дополнительную строчку, а друзьям по цеху предоставляется в качестве самостоятельного упражнения :-).