Skip to content

Instantly share code, notes, and snippets.

@temirlanKabylbekov
Last active March 13, 2021 06:20
Show Gist options
  • Save temirlanKabylbekov/b7f11eaff3eb9ba9a617451b27d741a4 to your computer and use it in GitHub Desktop.
Save temirlanKabylbekov/b7f11eaff3eb9ba9a617451b27d741a4 to your computer and use it in GitHub Desktop.
Алгоритмы сортировок
# 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