Сообщение Re[2]: quicksort или не quicksort от 29.10.2015 7:44
Изменено 29.10.2015 7:45 Evgeny.Panasyuk
Здравствуйте, Буравчик, Вы писали:
Б>Наврядли удастся это сделать, пока не будет обозначено четкое определение quicksort
Более-менее чёткое определение выводится из оригинальной статьи. Inplace является одной из главных составляющих скорости сортировки.
Даже название нам указывает на то, что скорость является важным атрибутом этой сортировки.
Б>2. Сложность O(N*logN)
В оригинальном quicksort глубина стэка гарантированно логарифмическая.
Б>Есть конечно нюансы, но это вопрос реализации:
Б>1. Для "настоящего" quicksort не нужна дополнительная память (in-place сортировка), но в Haskell такое понятие вообще не имеет смысла.
Есть монадические массивы с inplace модификацией. Вот пример того как это выглядит — уже не так радужно.
Б>Одновременно эти два условия и не соблюсти — stable in-place за O(N*logN) пока не придумали
Есть адаптивные stable сортировки на базе merge. Если доступен дополнительный объём памяти в "несколько процентов" от объёма входного массива — то сложность O(N*ln(N). Если же нет (полностью inplace) то O(N*ln2(N)). Этот алгоритм подробно разбирает Александров Степанов в Elements of Programming, и он используется в реализациях std::stable_sort.
Б>И не забываем, что в Haskell сортируется список, т.е. структура с последовательным доступом (в отличии от массива)
Не просто последовательным, а ещё и однонаправленным. Более-менее нормальный quicksort можно реализовать для двунаправленных последовательностей.
Б>Наврядли удастся это сделать, пока не будет обозначено четкое определение quicksort
Более-менее чёткое определение выводится из оригинальной статьи. Inplace является одной из главных составляющих скорости сортировки.
Даже название нам указывает на то, что скорость является важным атрибутом этой сортировки.
Б>2. Сложность O(N*logN)
В оригинальном quicksort глубина стэка гарантированно логарифмическая.
Б>Есть конечно нюансы, но это вопрос реализации:
Б>1. Для "настоящего" quicksort не нужна дополнительная память (in-place сортировка), но в Haskell такое понятие вообще не имеет смысла.
Есть монадические массивы с inplace модификацией. Вот пример того как это выглядит — уже не так радужно.
Б>Одновременно эти два условия и не соблюсти — stable in-place за O(N*logN) пока не придумали
Есть адаптивные stable сортировки на базе merge. Если доступен дополнительный объём памяти в "несколько процентов" от объёма входного массива — то сложность O(N*ln(N). Если же нет (полностью inplace) то O(N*ln2(N)). Этот алгоритм подробно разбирает Александров Степанов в Elements of Programming, и он используется в реализациях std::stable_sort.
Б>И не забываем, что в Haskell сортируется список, т.е. структура с последовательным доступом (в отличии от массива)
Не просто последовательным, а ещё и однонаправленным. Более-менее нормальный quicksort можно реализовать для двунаправленных последовательностей.
Re[2]: quicksort или не quicksort
Здравствуйте, Буравчик, Вы писали:
Б>Наврядли удастся это сделать, пока не будет обозначено четкое определение quicksort
Более-менее чёткое определение выводится из оригинальной статьи. Inplace является одной из главных составляющих скорости сортировки.
Даже название нам указывает на то, что скорость является важным атрибутом этой сортировки.
Б>2. Сложность O(N*logN)
В оригинальном quicksort глубина стэка гарантированно логарифмическая.
Б>Есть конечно нюансы, но это вопрос реализации:
Б>1. Для "настоящего" quicksort не нужна дополнительная память (in-place сортировка), но в Haskell такое понятие вообще не имеет смысла.
Есть монадические массивы с inplace модификацией. Вот пример того как это выглядит — уже не так радужно.
Б>Одновременно эти два условия и не соблюсти — stable in-place за O(N*logN) пока не придумали
Есть адаптивные stable сортировки на базе merge. Если доступен дополнительный объём памяти в "несколько процентов" от объёма входного массива — то сложность O(N*ln(N)). Если же нет (полностью inplace) то O(N*ln2(N)). Этот алгоритм подробно разбирает Александров Степанов в Elements of Programming, и он используется в реализациях std::stable_sort.
Б>И не забываем, что в Haskell сортируется список, т.е. структура с последовательным доступом (в отличии от массива)
Не просто последовательным, а ещё и однонаправленным. Более-менее нормальный quicksort можно реализовать для двунаправленных последовательностей.
Б>Наврядли удастся это сделать, пока не будет обозначено четкое определение quicksort
Более-менее чёткое определение выводится из оригинальной статьи. Inplace является одной из главных составляющих скорости сортировки.
Даже название нам указывает на то, что скорость является важным атрибутом этой сортировки.
Б>2. Сложность O(N*logN)
В оригинальном quicksort глубина стэка гарантированно логарифмическая.
Б>Есть конечно нюансы, но это вопрос реализации:
Б>1. Для "настоящего" quicksort не нужна дополнительная память (in-place сортировка), но в Haskell такое понятие вообще не имеет смысла.
Есть монадические массивы с inplace модификацией. Вот пример того как это выглядит — уже не так радужно.
Б>Одновременно эти два условия и не соблюсти — stable in-place за O(N*logN) пока не придумали
Есть адаптивные stable сортировки на базе merge. Если доступен дополнительный объём памяти в "несколько процентов" от объёма входного массива — то сложность O(N*ln(N)). Если же нет (полностью inplace) то O(N*ln2(N)). Этот алгоритм подробно разбирает Александров Степанов в Elements of Programming, и он используется в реализациях std::stable_sort.
Б>И не забываем, что в Haskell сортируется список, т.е. структура с последовательным доступом (в отличии от массива)
Не просто последовательным, а ещё и однонаправленным. Более-менее нормальный quicksort можно реализовать для двунаправленных последовательностей.