George_Zagorsky_1

Untitled

Jan 16th, 2022
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.76 KB | None | 0 0
  1. # method двух указателей основаный на оптимальном квиксорте
  2.  
  3. def merge_sort(left, right):
  4.     i = j = 0
  5.     stack = []
  6.     while i < len(left) and j < len(right):
  7.         if left[i] < right[j]:
  8.             stack.append(left[i])
  9.             i += 1
  10.         else:
  11.             stack.append(right[j])
  12.             j += 1
  13.     while i < len(left):
  14.         stack.append(left[i])
  15.         i += 1
  16.     while j < len(right):
  17.         stack.append(right[j])
  18.         j += 1
  19.     return stack
  20.  
  21.  
  22. def razbienie(array):
  23.     if len(array) < 2:
  24.         return array
  25.     else:
  26.         index = len(array) // 2
  27.         left = razbienie(array[:index])
  28.         right = razbienie(array[index:])
  29.         return merge_sort(left, right)
  30.  
  31.  
  32. def quick_sort(array):
  33.     if len(array) < 2:
  34.         return array
  35.     elif len(array) < 32:
  36.         array = razbienie(array)
  37.         return array
  38.     else:
  39.         element = array[len(array) // 2]
  40.         left = [x for x in array if x < element]
  41.         middle = [x for x in array if x == element]
  42.         right = [x for x in array if x > element]
  43.         return quick_sort(left) + middle + quick_sort(right)
  44.  
  45.  
  46. def double_ukazatelia(array, digit):
  47.     i = 0
  48.     j = len(array) - 1
  49.     while i <= j:
  50.         if array[i] + array[j] < digit:
  51.             i += 1
  52.         elif array[i] + array[j] > digit:
  53.             j -= 1
  54.         else:
  55.             return ('We found your digit as summ of 2 digits -> ', array[i], array[j])
  56.  
  57.     return False
  58.  
  59.  
  60. array = list(map(int, input().split()))  # inter your list for sorting
  61.  
  62. print(quick_sort(array))
  63.  
  64. digit_for_answer = int(input('Print digit that we need to find as summ of 2 digits   ___ >  '))
  65.  
  66. print(double_ukazatelia(array, digit_for_answer))
  67.  
Advertisement
Add Comment
Please, Sign In to add comment