Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- hlyakhtin_Maksim_lb2/src/main.py
- @@ -0,0 +1,86 @@
- def calcMinRun(n):
- r = 0
- while n >= 64:
- r |= n & 1
- n >>= 1
- return n + r
- def cmp(a, b):
- if a ** 2 < b ** 2 or a ** 2 == b ** 2 and a > b:
- return True
- return False
- def insertion_sort(arr, left, right):
- if len(arr) <= 1:
- return
- for i in range(left + 1, right):
- j = i
- while j > left and cmp(arr[j], arr[j - 1]):
- arr[j], arr[j - 1] = arr[j - 1], arr[j]
- j -= 1
- def merge_sort(arr):
- if len(arr) == 1 or len(arr) == 0:
- return arr
- arr_l = merge_sort(arr[:len(arr) // 2])
- arr_r = merge_sort(arr[len(arr) // 2:])
- res_arr = [0] * (len(arr_l) + len(arr_r))
- arr_l_count = 0
- arr_r_count = 0
- res_count = 0
- while arr_r_count < len(arr_r) and arr_l_count < len(arr_l):
- if arr_l[arr_l_count] ** 2 < arr_r[arr_r_count] ** 2:
- res_arr[res_count] = arr_l[arr_l_count]
- arr_l_count += 1
- elif arr_l[arr_l_count] ** 2 > arr_r[arr_r_count] ** 2:
- res_arr[res_count] = arr_r[arr_r_count]
- arr_r_count += 1
- elif arr_l[arr_l_count] ** 2 == arr_r[arr_r_count] ** 2:
- if arr_l[arr_l_count] >= arr_r[arr_r_count]:
- res_arr[res_count] = arr_l[arr_l_count]
- arr_l_count += 1
- else:
- res_arr[res_count] = arr_r[arr_r_count]
- arr_r_count += 1
- res_count += 1
- while arr_l_count < len(arr_l):
- res_arr[res_count] = arr_l[arr_l_count]
- arr_l_count += 1
- res_count += 1
- while arr_r_count < len(arr_r):
- res_arr[res_count] = arr_r[arr_r_count]
- arr_r_count += 1
- res_count += 1
- for i in range(len(res_arr)):
- arr[i] = res_arr[i]
- return arr
- def timsort(arr, minRun=32):
- n = len(arr)
- i = 0
- for start in range(0, n, minRun):
- end = min(start + minRun, n)
- insertion_sort(arr, start, end)
- if start != end:
- print(f"Part {i}:", *arr[start:end])
- else:
- print(f"Part {i}:", arr[start])
- i += 1
- merge_sort(arr)
- n = int(input())
- arr = list(map(int, input().split()))
- timsort(arr)
- print("Answer:", *arr)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement