Last active
March 13, 2021 06:20
-
-
Save temirlanKabylbekov/b7f11eaff3eb9ba9a617451b27d741a4 to your computer and use it in GitHub Desktop.
Алгоритмы сортировок
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# coding: utf8 | |
def selection_sort(arr): | |
for idx in range(len(arr)): | |
min_idx = idx | |
for jdx in range(idx + 1, len(arr)): | |
if arr[min_idx] > arr[jdx]: | |
min_idx = jdx | |
arr[idx], arr[min_idx] = arr[min_idx], arr[idx] | |
return arr | |
def insertion_sort(arr): | |
for idx in range(1, len(arr)): | |
key = arr[idx] | |
jdx = idx - 1 | |
while jdx >= 0 and key < arr[jdx]: | |
arr[jdx + 1] = arr[jdx] | |
jdx -= 1 | |
arr[jdx + 1] = key | |
return arr | |
def bubble_sort(arr): | |
for idx in range(len(arr)): | |
for jdx in range(len(arr) - idx - 1): | |
if arr[jdx] > arr[jdx + 1]: | |
arr[jdx], arr[jdx + 1] = arr[jdx + 1], arr[jdx] | |
return arr | |
def sift_down(arr, n, idx): | |
""" | |
Спускает меньший элемент вниз в max-heap | |
Если i-й элемент больше, чем его сыновья, всё поддерево уже является | |
кучей, и делать ничего не надо. В противном случае меняем местами i-й | |
элемент с наибольшим из его сыновей, после чего выполняем sift down | |
для этого сына. | |
""" | |
largest = idx | |
left = 2 * idx + 1 | |
right = 2 * idx + 2 | |
if left < n and arr[largest] < arr[left]: | |
largest = left | |
if right < n and arr[largest] < arr[right]: | |
largest = right | |
if largest != idx: | |
arr[idx], arr[largest] = arr[largest], arr[idx] | |
sift_down(arr, n, largest) | |
def heap_sort(arr): | |
# строим max-heap | |
for idx in range(len(arr) // 2 - 1, -1, -1): | |
sift_down(arr, len(arr), idx) | |
# n - 1 достаем max элемент и кладем на освободившееся место | |
# берем максимум из левой части, кладем в конец левой части | |
for idx in range(len(arr) - 1, 0, -1): | |
arr[idx], arr[0] = arr[0], arr[idx] | |
sift_down(arr, idx, 0) | |
return arr | |
def merge(arr, left, mid, right): | |
left_arr = [arr[left + idx] for idx in range(mid - left + 1)] | |
right_arr = [arr[mid + 1 + idx] for idx in range(right - mid)] | |
left_idx = 0 | |
right_idx = 0 | |
merge_idx = left | |
while left_idx < len(left_arr) and right_idx < len(right_arr): | |
if left_arr[left_idx] <= right_arr[right_idx]: | |
arr[merge_idx] = left_idx | |
left_idx += 1 | |
else: | |
arr[merge_idx] = right_arr[right_idx] | |
right_idx += 1 | |
merge_idx += 1 | |
while left_idx < len(left_arr): | |
arr[merge_idx] = left_arr[left_idx] | |
left_idx += 1 | |
merge_idx += 1 | |
while right_idx < len(right_arr): | |
arr[merge_idx] = right_arr[right_idx] | |
right_idx += 1 | |
merge_idx += 1 | |
def merge_sort(arr): | |
def util(arr, left, right): | |
if left >= right: | |
return arr | |
mid = left + (right - left) // 2 | |
util(arr, left, mid) | |
util(arr, mid + 1, right) | |
merge(arr, left, mid, right) | |
return arr | |
return util(arr, 0, len(arr) - 1) | |
def partition(array, start, end): | |
pivot = array[start] | |
low = start + 1 | |
high = end | |
while True: | |
while low <= high and array[high] >= pivot: | |
high = high - 1 | |
while low <= high and array[low] <= pivot: | |
low = low + 1 | |
if low <= high: | |
array[low], array[high] = array[high], array[low] | |
else: | |
break | |
array[start], array[high] = array[high], array[start] | |
return high | |
def quick_sort(arr): | |
def util(arr, start, end): | |
if start >= end: | |
return arr | |
p = partition(arr, start, end) | |
util(arr, start, p-1) | |
util(arr, p+1, end) | |
return arr | |
return util(arr, 0, len(arr) - 1) | |
MIN_MERGE = 64 | |
def get_tim_sort_min_run(n): | |
""" | |
len(array) / minrun - около степени двойки | |
""" | |
r = 0 | |
while n >= MIN_MERGE: | |
r |= n & 1 | |
n >>= 1 | |
return n + r | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment