istomina_sofia

питон лаба2

Dec 20th, 2022
1,018
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.70 KB | None | 0 0
  1. import random
  2. import math
  3. import time
  4. import sys
  5.  
  6. sys.setrecursionlimit(15000)
  7.  
  8. array = [random.randint(0, 10) for i in range(1000)]
  9.  
  10. def chelnok(array):
  11.     array_new = array.copy()
  12.     for i in range(len(array_new)):
  13.         for j in range(i, 0, -1):
  14.             if array_new[j] < array_new[j-1]:
  15.                 array_new[j], array_new[j-1] = array_new[j-1], array_new[j]
  16.         for j in range(i):
  17.             if array_new[j] > array_new[j+1]:
  18.                 array_new[j], array_new[j+1] = array_new[j+1], array_new[j]
  19.     return(array_new)
  20.  
  21. def Shell(array):
  22.     a = array.copy()
  23.     k = int(math.log2(len(a)))
  24.     arange = 2**k-1
  25.     while arange > 0:
  26.         for i in range(arange, len(a)):
  27.             buff = a[i]
  28.             j = i
  29.             while (j>=arange) and (a[j-arange]>buff):
  30.                 a[j] = a[j-arange]
  31.                 j-=arange
  32.             a[j] = buff
  33.         k-=1
  34.         arange = 2**k-1
  35.     return(a)
  36.  
  37.  
  38.  
  39. def quicksort(array):
  40.     if len(array) < 2:
  41.         return(array)
  42.     pivot = array[int(len(array)/2)]
  43.     left = []
  44.     pivots = []
  45.     right = []
  46.     for i in array:
  47.         if i < pivot:
  48.             left.append(i)
  49.         elif i == pivot:
  50.             pivots.append(i)
  51.         else:
  52.             right.append(i)
  53.     return(quicksort(left) + pivots + quicksort(right))
  54.  
  55.  
  56.        
  57.        
  58.  
  59.    
  60.  
  61.  
  62. def insertion_sort(array):
  63.     median = array[0]
  64.     a = [median]
  65.     median_index = 0
  66.     for i in range(1, len(array)):
  67.         if array[i] > median:
  68.             if median_index == len(a)-1:
  69.                 a.append(array[i])
  70.             else:
  71.                 for j in range(median_index, len(a)):
  72.                     if array[i] <= a[j]:
  73.                         a.insert(j, array[i])
  74.                         break
  75.                     else:
  76.                         if j == len(a)-1:
  77.                             a.append(array[i])
  78.         elif array[i] < median:
  79.             if median_index == 0:
  80.                 a.insert(0, array[i])
  81.                 median_index+=1
  82.             else:
  83.                 for j in range(median_index, -1, -1):
  84.                     if array[i] >= a[j]:  
  85.                         a.insert(j+1, array[i])
  86.                         break
  87.                     else:
  88.                         if j == 0:
  89.                             a.insert(0, array[i])
  90.                 median_index+=1
  91.         elif array[i] == median:
  92.             a.insert(median_index, array[i])
  93.             median_index +=1
  94.     return(a)
  95.  
  96. def binary(array, a):
  97.     left_index = int(0)
  98.     right_index = len(array)-1
  99.    
  100.     while left_index <= right_index:
  101.         median = int((left_index+right_index)/2)
  102.  
  103.         if a < array[median]:
  104.             right_index = median-1
  105.        
  106.         elif a > array[median]:
  107.             left_index = median+1
  108.  
  109.         elif a == array[median]: return(a)
  110.  
  111.     return("Error")
  112.  
  113.  
  114.  
  115. def binary_recurs(array, a, left_index = 0, right_index = None):
  116.     if right_index == None: right_index = len(array)-1
  117.    
  118.     median = (left_index+right_index)//2
  119.  
  120.     if (left_index == right_index) and (array[left_index]!=a): return("Error")
  121.     elif a == array[median]: return(a)
  122.     elif a < array[median]: right_index = median-1
  123.     else: left_index = median +1
  124.     return(binary_recurs(array, a, left_index, right_index))
  125.    
  126.    
  127.  
  128. def interpolation(array, a):
  129.  
  130.     left_index = 0
  131.     right_index = len(array)-1
  132.  
  133.     while (left_index <= right_index) and (a <= array[right_index]) and (a >= array[left_index]):
  134.  
  135.         median = int(left_index + ((a-array[left_index])*(right_index-left_index) / (array[right_index]- array[left_index])))
  136.        
  137.         if array[median] == a:
  138.             return(a)
  139.        
  140.         if a < array[median]:
  141.             right_index = median - 1
  142.  
  143.         else:
  144.             left_index = median + 1
  145.            
  146.    
  147.     return("Error")
  148.  
  149.        
  150.  
  151.  
  152. def test(array, sort_method, find_method):
  153.     time1 = time.time()
  154.     for i in range(10):
  155.         find_method(sort_method(array), random.randint(0, 10))
  156.     time2 = time.time()
  157.     return(time2-time1)
  158.  
  159.  
  160.  
  161. print(f'Челночная сортировка и бинарный поиск 100 раз: {test(array, chelnok, binary)}с')
  162. print(f'Сортировка шелла и бинарный рекурсивный поиск 100 раз: {test(array, Shell, binary_recurs)}с')
  163. print(f'Быстрая сортировка и бинарный поиск по 100 раз: {test(array, quicksort, binary)}с')
  164. print(f'Сортировка центрированной вставкой и интерполяционный поиск по 100 раз: {test(array, insertion_sort, interpolation)}c')
Advertisement
Add Comment
Please, Sign In to add comment