Ниже представлена таблица сравнительного анализа скорости сортировки, при использовании разных алгоритмов. На вход подавался список из случайно сгенерированных чисел в интервале от 0 до 99, длинна списка — 10000. Замер скорости при помощи встроенного python модуля timeit
№ |
Алгоритм сортировки | Затраченное на сортировку время (сек.) |
1 | Пузырьком | 54.965114210004685 |
2 | Вставкой | 26.21249842699035 |
3 | Слиянием | 0.5282726000004914 |
4 | Быстрая | 0.054333254985976964 |
Содержание статьи
Сортировка пузырьком
def bubble_sort(array): n = len(array) for i in range(n): already_sorted = True for j in range(n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] already_sorted = False if already_sorted: break return array
Более простая реализация
def bubble_sort(array): n = len(array) for i in range(n): for j in range(n-1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] return array
Сортировка вставкой
def insertion_sort(array): for i in range(1, len(array)): key_item = array[i] j = i - 1 while j >= 0 and array[j] > key_item: array[j + 1] = array[j] j -= 1 array[j + 1] = key_item return array
Сортировка слиянием
def merge(left, right): if len(left) == 0: return right if len(right) == 0: return left result = [] index_left = index_right = 0 while len(result) < len(left) + len(right): if left[index_left] <= right[index_right]: result.append(left[index_left]) index_left += 1 else: result.append(right[index_right]) index_right += 1 if index_right == len(right): result += left[index_left:] break if index_left == len(left): result += right[index_right:] break return result def merge_sort(array): if len(array) < 2: return array midpoint = len(array) // 2 return merge( left=merge_sort(array[:midpoint]), right=merge_sort(array[midpoint:]))
Быстрая сортировка
Алгоритм быстрой сортировки на python с применением рекурсии.
from random import randint def quicksort(array): if len(array) < 2: return array low, same, high = [], [], [] pivot = array[randint(0, len(array) - 1)] for item in array: if item < pivot: low.append(item) elif item == pivot: same.append(item) elif item > pivot: high.append(item) return quicksort(low) + same + quicksort(high)