Сообщение Re[5]: quicksort или не quicksort от 29.10.2015 13:21
Изменено 29.10.2015 13:58 _DAle_
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Это их фейл.
EP>Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18):
EP>https://youtu.be/d4tFGtGngf4?t=2058
EP>ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал.
Окей. Я не согласен. Я считаю, что тот конкретный алгоритм, который когда-то описал Хоар — это одна из реализаций того, что сейчас называется Quicksort (а та конкретная называется сортировкой Хоара). На мой взгляд, сейчас (а не в прошлом веке) по термином Quicksort подразумевают семейство алгоритмов (например, в той же википедии это так), с конкретным подходом: divide and conquer + pivot, и вполне определенной временной сложностью по времени в среднем и худшем случае.
Если считать, что, например, Lomuto partition — это уже не Quicksort, не in-place реализация — не Quicksort, тогда отсутствие хвостовой рекурсии — это тоже не Quicksort? А переход на insertion sort для малых интервалов — это Quicksort или нет? Если Quicksort — это только то, что Хоар описал в 60-х, так она тогда на практике и не используется нигде (в модуле turbo pascal разве что
.
В целом, я за позицию wikipedia и Кормена et al.
EP>Это их фейл.
EP>Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18):
EP>https://youtu.be/d4tFGtGngf4?t=2058
EP>ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал.
Окей. Я не согласен. Я считаю, что тот конкретный алгоритм, который когда-то описал Хоар — это одна из реализаций того, что сейчас называется Quicksort (а та конкретная называется сортировкой Хоара). На мой взгляд, сейчас (а не в прошлом веке) по термином Quicksort подразумевают семейство алгоритмов (например, в той же википедии это так), с конкретным подходом: divide and conquer + pivot, и вполне определенной временной сложностью по времени в среднем и худшем случае.
Если считать, что, например, Lomuto partition — это уже не Quicksort, не in-place реализация — не Quicksort, тогда отсутствие хвостовой рекурсии — это тоже не Quicksort? А переход на insertion sort для малых интервалов — это Quicksort или нет? Если Quicksort — это только то, что Хоар описал в 60-х, так она тогда на практике и не используется нигде (в модуле turbo pascal разве что
. В целом, я за позицию wikipedia и Кормена et al.
Re[5]: quicksort или не quicksort
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Это их фейл.
EP>Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18):
EP>https://youtu.be/d4tFGtGngf4?t=2058
EP>ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал.
Окей. Я не согласен. Я считаю, что тот конкретный алгоритм, который когда-то описал Хоар — это одна из реализаций того, что сейчас называется Quicksort (а та конкретная называется сортировкой Хоара). На мой взгляд, сейчас (а не в прошлом веке) по термином Quicksort подразумевают семейство алгоритмов (например, в той же википедии это так), с конкретным подходом: divide and conquer + pivot, и вполне определенной временной сложностью по времени в среднем и худшем случае.
Если считать, что, например, Lomuto partition — это уже не Quicksort, не in-place реализация — не Quicksort, тогда отсутствие хвостовой рекурсии — это тоже не Quicksort? А переход на insertion sort для малых интервалов — это Quicksort или нет? Если Quicksort — это только то, что Хоар описал в 60-х, так она тогда на практике и не используется нигде (в модуле turbo pascal разве что.. а хотя стойте, там же нет хвостовой рекурсии
).
В целом, я за позицию wikipedia и Кормена et al.
EP>Это их фейл.
EP>Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18):
EP>https://youtu.be/d4tFGtGngf4?t=2058
EP>ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал.
Окей. Я не согласен. Я считаю, что тот конкретный алгоритм, который когда-то описал Хоар — это одна из реализаций того, что сейчас называется Quicksort (а та конкретная называется сортировкой Хоара). На мой взгляд, сейчас (а не в прошлом веке) по термином Quicksort подразумевают семейство алгоритмов (например, в той же википедии это так), с конкретным подходом: divide and conquer + pivot, и вполне определенной временной сложностью по времени в среднем и худшем случае.
Если считать, что, например, Lomuto partition — это уже не Quicksort, не in-place реализация — не Quicksort, тогда отсутствие хвостовой рекурсии — это тоже не Quicksort? А переход на insertion sort для малых интервалов — это Quicksort или нет? Если Quicksort — это только то, что Хоар описал в 60-х, так она тогда на практике и не используется нигде (в модуле turbo pascal разве что.. а хотя стойте, там же нет хвостовой рекурсии
). В целом, я за позицию wikipedia и Кормена et al.