Код алгоритмов сортировки:
import numpy as np
def selection_sort(a):
length = len(a)
for i in range(length - 1):
index = i
for j in range(i+1, length):
if a[j] < a[index]:
index = j
a[i], a[index] = a[index], a[i]
def insertion_sort(a):
for i in range(1, len(a)):
j = i
save = a[j]
while j > 0 and a[j-1] > save:
a[j] = a[j-1]
j -= 1
a[j] = save
def bubble_sort(a):
is_sorted = False
j = len(a) - 1
while not is_sorted:
is_sorted = True
for i in range(j):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i]
is_sorted = False
j -= 1
def quick_sort(a):
if not a:
return a
x = np.random.choice(a)
left = [i for i in a if i < x]
mid = [i for i in a if i == x]
right = [i for i in a if i > x]
return quick_sort(left) + mid + quick_sort(right)
a = list(np.random.randint(0, 10, 1000))
%timeit selection_sort(a)
a = list(np.random.randint(0, 10, 1000))
%timeit insertion_sort(a)
a = list(np.random.randint(0, 10, 1000))
%timeit bubble_sort(a)
a = list(np.random.randint(0, 10, 1000))
%timeit quick_sort(a)
Python 3.7.11 выдает примерно следующие результаты:
28.3 ms ± 182 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) # selection_sort
135 µs ± 2.36 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) # insertion_sort
80.7 µs ± 302 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) # bubble_sort
391 µs ± 4.93 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) # quick_sort
Что не так с реализацией алгоритма quick_sort?
