Я смотрел на различные алгоритмы сортировки и их производительность ( ссылка ), а затем я попытался реализовать некоторые алгоритмы сортировки самостоятельно. Я также хотел улучшить их, и поэтому, поскольку я кодировал сортировку вставок, я подумал, почему бы не использовать бинарный поиск, так как первая часть массива уже отсортирована, а для того, чтобы избавиться от свопов, использовать дополнительный массив , Код можно найти на моем GitHub или здесь:
def insertion_sort_optimized(arr):
array = [arr[0]]
for i in range(1, len(arr)):
index = bisect_left(array, i)
array.insert(index, i)
return array
И тогда я реализовал Quicksort как обычно ( ссылка ):
def quicksort(arr):
if len(arr) <= 1:
return arr
smaller_part = []
larger_part = []
pivot = arr[len(arr) - 1]
for i in range(len(arr) - 1):
if arr[i] < pivot:
smaller_part.append(arr[i])
else:
larger_part.append(arr[i])
return quicksort(smaller_part) + [pivot] + quicksort(larger_part)
А затем я сгенерировал случайный массив из 1.000.000 чисел и сравнил производительность обоих из них, используя эту вспомогательную функцию :
def test_sorting_algorithm(sort=None, version="normal", returns=False, n=1000000):
if version.lower() == "normal":
print("Normal version:")
else:
print("Optimized version:")
arr = [int(random() * n) for _ in range(n)]
print(arr)
start = time.time()
if returns:
arr = sort(arr)
else:
sort(arr)
end = time.time()
print(arr)
print(f"Time elapsed: {end - start}\n")
Таким образом, он в основном выполняет заданную sort функция и печатает сколько времени заняло сортировку массива. И поэтому я выполнял этот код по крайней мере 10 раз, и сортировка двоичной вставки была почти в 9 раз быстрее (9 с> 1 с) каждый раз. Но я подумал, что быстрая сортировка была самой быстрой ... И если бы я сравнил эти 2 алгоритма сортировки, я бы сказал, что сортировка с двоичной вставкой лучше, хотя она занимает O (n) дополнительного пространства (худшая временная сложность будет O (n *). log (n)), что лучше, чем Quicksort ...). Это ошибка? Quicksort на самом деле хуже двоичной сортировки с вставкой? Я пытался найти его по всему Inte rnet, но не смог найти что-то действительно похожее на мой код. Может быть, это даже не двоичная вставка, а скорее что-то еще ... (другое имя)?