- 1
- 2
- 3
- 4
from random import randint
def qsort(l, rnd=0):
return (qsort([x for x in l if x < l[rnd]], rnd=randint(0, len([x for x in l if x < l[rnd]]) - 1) if [x for x in l if x < l[rnd]] else -1) + [x for x in l if x == l[rnd]] + qsort([x for x in l if x > l[rnd]], rnd=randint(0, len([x for x in l if x > l[rnd]]) - 1) if [x for x in l if x > l[rnd]] else -1)) if len(l) > 1 else l
P.S. Сгенерённый код случаем не экспоненциально растёт от N?
Код работает за K * N * log(N).
Где K константа примерно равная 10.
return qsort([x for x in l if x < l[0]]) + [x for x in l if x == l[0]] + qsort([x for x in l if x > l[0]]) if l else []
тоже вариант
Чувак, в питоне встроенный алгоритм сортировки не квик сорт, а timsort
а иной нет
Ну и
гость тащемто прав. Олсо я тут задумался, а стабилен ли квиксорт в STL... Я столько кода на него завязал уже, а никогда об этом не задумывался... Вот жеж блин...