• fp То ли я чего-то не понимаю, но почему всякие хаскели и скалы пишут квиксорт примерно таким образом?

    def sortList(list: List[Int]): List[Int] = list match {
    case Nil => Nil
    case head :: tail => sortList(tail.filter(_ < head)) ::: head :: sortList(tail.filter(_ >= head))
    }

    В смысле, разве этот .filter() будет проходить не два раза по одному и тому же списку? Разве не правильнее сделать какой-нибудь split, возвращающий тупл из элементов "больше" и "меньше", и тут уже правильно их распихать?

    Ну и вообще надо бы поисследовать что еще там такого, что тормозит jazzy.id.au

Replies (2)

  • @kb, и да, под "split" я имел в виду Data.List.span (в случае с х-лем)
  • @kb, Потому что, это якобы такой завлекающий маневр — простой и сжатый (concise) пример, чтобы обратить новопришедших. mergesort на списках должен быть пошустрее, вероятно.
    но в любом случае квиксорт (на списках) будет создавать O(n * log(n)) мусора, в лучшем случае, что гораздо груснее чем двойной проход.