Является ли эта быстрая сортировка стабильной?

Я вот что сложно сделать стабильной быстрой сортировкой. Однако моя быстрая сортировка кажется стабильной.

quicksortBy _ []=[]
quicksortBy key (pivot:rest)=
    (quicksortBy key [little|little<-rest, key little < key pivot])
    ++ [pivot] ++
    (quicksortBy key [big|big<-rest, key big >= key pivot])

Затем я делаю:

*Main> let items = [(4,0),(1,1),(10,2),(6,3),(4,4),(6,5), (1,6)]
*Main> quicksortBy fst items
[(1,1),(1,6),(4,0),(4,4),(6,3),(6,5),(10,2)]

Используя первый элемент в качестве опорного, дубликаты перемещаются вправо. Это неправильно, или люди не используют это, так как это неэффективно для отсортированных данных. Или я открыл для себя что-то новое?


quicksort
person PyRulez    schedule 14.12.2013    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Да, описанный вами алгоритм стабилен, и его обычно называют «наивной» быстрой сортировкой. Проблема этого алгоритма в том, что для сортировки массива требуется O(n) дополнительного пространства. Более экономичные версии быстрой сортировки используют свопы на месте для изменения массива, что разрушает стабильность, но снижает стоимость пространства до O(log n) — фактически просто стек рекурсивных вызовов.

person Martin O'Leary    schedule 14.12.2013

arrow_upward
1
arrow_downward

Причина, по которой ваша быстрая сортировка стабильна, заключается в том, что (поскольку вы используете функциональный язык) она копирует элементы (по порядку) в новый массив или три на каждом шаге. Это довольно неэффективно как во времени, так и в пространстве, но (как вы обнаружили) стабильно. Более эффективная быстрая сортировка с использованием изменяемых массивов разделяет массив на месте снаружи внутрь, что требует только одного прохода по массиву на каждом уровне и использует только один дополнительный элемент памяти для замены элементов (и, в случае целочисленного массива, может на самом деле обойти даже это, используя своп xor).

person Kevin    schedule 14.12.2013

arrow_upward
1
arrow_downward

Да, стабильно. Внутренний цикл Quicksort очень эффективен, поэтому ваш алгоритм также может быть быстрее, чем другие стабильные алгоритмы сортировки, такие как сортировка слиянием, хотя, я думаю, вероятность этого мала. Недостатком является то, что он занимает больше места, чем сортировка слиянием (в том числе и для хранения индексов). И, глядя на функцию сравнения, я предполагаю, что она будет очень плохо работать с массивами со многими эквивалентными ключами, потому что для каждого из них потребуется две ветви.

В общем, свободно исследуйте и просто используйте сортировку слиянием в приложении.

person Calvin Caulfield    schedule 15.12.2013