?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

(no subject)
nyaload
_winnie
Интересно, когда демонстрируют "красоту" написания QuickSort на языках со списками, то в качестве разделяющего элемента берут первый. А не середину (или среднее из тройки последний-середина-первый, как во многих сишных реализациях). В результате на упорядоченых последовательностях оно себя ведёт совсем не Quick. Чего только не сделаешь для для демонстрации красоты какой-либо концепции ;)
Ну и теряют основную фишку QuickSort - оно по-джентельменски ведёт себя с памятью, читая последовательно из двух мест. Собствено почему оно и названо Quick, несмотря на типичный NlogN и N^2 в худшем случае.

отсортировать(список)
  head = первый элемент списка
  tail = остальные кроме первого
  вернуть (отсортировать[элементы tail меньше head]) [head] (отсортировать [элементы tail больше или равные x])


Не используйте этот пример из учебника в реальной жизни, библиотечная функция вряд ли будет написана в ущерб скорости ради красоты.

upd: забыл про рекурсивный вызов, вставил.