python quicksort - Можно ли улучшить этот код?

Question

Вы можете посоветовать, как улучшить этот код?

def qsort(arr):
    if len(arr) < 2:
        return arr
    else:
        root =  arr[round(len(arr)/2)]
        arr.remove(root)
        min_  = [i for i in arr if i <  root]
        max_  = [i for i in arr if i >  root]
        oth_  = [i for i in arr if i == root]
        return  qsort(min_) + [root]+oth_ + qsort(max_)

Answer 1

Я могу думать о двух вещах, которые могут повысить эффективность этого кода. Первый - использовать один l oop с тремя условиями i root и i == root, как операторы if / elif / else в качестве тела вместо использования понимания списка для каждого состояние. Это сократит количество касаний каждого элемента массива с примерно 3 до примерно 1.

Вторая вещь - это удаление root из массива. Вы не достигнете sh слишком многого, сделав это (вы можете просто получить индекс root и ссылку arr [root_index] всякий раз, когда вам понадобится root), а удаление элемента из середины массива может быть в некоторой степени дорогостоящая операция в Python (поскольку вы не получаете индекс, вы на самом деле снова ищете в массиве root, затем удаляете его, а затем перемещаете все в индексе выше, чем root, вниз на индекс). Не забывайте не учитывать его дважды, если вы решите не удалять его из массива.