Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import random
- import math
- import time
- import sys
- sys.setrecursionlimit(15000)
- array = [random.randint(0, 10) for i in range(1000)]
- def chelnok(array):
- array_new = array.copy()
- for i in range(len(array_new)):
- for j in range(i, 0, -1):
- if array_new[j] < array_new[j-1]:
- array_new[j], array_new[j-1] = array_new[j-1], array_new[j]
- for j in range(i):
- if array_new[j] > array_new[j+1]:
- array_new[j], array_new[j+1] = array_new[j+1], array_new[j]
- return(array_new)
- def Shell(array):
- a = array.copy()
- k = int(math.log2(len(a)))
- arange = 2**k-1
- while arange > 0:
- for i in range(arange, len(a)):
- buff = a[i]
- j = i
- while (j>=arange) and (a[j-arange]>buff):
- a[j] = a[j-arange]
- j-=arange
- a[j] = buff
- k-=1
- arange = 2**k-1
- return(a)
- def quicksort(array):
- if len(array) < 2:
- return(array)
- pivot = array[int(len(array)/2)]
- left = []
- pivots = []
- right = []
- for i in array:
- if i < pivot:
- left.append(i)
- elif i == pivot:
- pivots.append(i)
- else:
- right.append(i)
- return(quicksort(left) + pivots + quicksort(right))
- def insertion_sort(array):
- median = array[0]
- a = [median]
- median_index = 0
- for i in range(1, len(array)):
- if array[i] > median:
- if median_index == len(a)-1:
- a.append(array[i])
- else:
- for j in range(median_index, len(a)):
- if array[i] <= a[j]:
- a.insert(j, array[i])
- break
- else:
- if j == len(a)-1:
- a.append(array[i])
- elif array[i] < median:
- if median_index == 0:
- a.insert(0, array[i])
- median_index+=1
- else:
- for j in range(median_index, -1, -1):
- if array[i] >= a[j]:
- a.insert(j+1, array[i])
- break
- else:
- if j == 0:
- a.insert(0, array[i])
- median_index+=1
- elif array[i] == median:
- a.insert(median_index, array[i])
- median_index +=1
- return(a)
- def binary(array, a):
- left_index = int(0)
- right_index = len(array)-1
- while left_index <= right_index:
- median = int((left_index+right_index)/2)
- if a < array[median]:
- right_index = median-1
- elif a > array[median]:
- left_index = median+1
- elif a == array[median]: return(a)
- return("Error")
- def binary_recurs(array, a, left_index = 0, right_index = None):
- if right_index == None: right_index = len(array)-1
- median = (left_index+right_index)//2
- if (left_index == right_index) and (array[left_index]!=a): return("Error")
- elif a == array[median]: return(a)
- elif a < array[median]: right_index = median-1
- else: left_index = median +1
- return(binary_recurs(array, a, left_index, right_index))
- def interpolation(array, a):
- left_index = 0
- right_index = len(array)-1
- while (left_index <= right_index) and (a <= array[right_index]) and (a >= array[left_index]):
- median = int(left_index + ((a-array[left_index])*(right_index-left_index) / (array[right_index]- array[left_index])))
- if array[median] == a:
- return(a)
- if a < array[median]:
- right_index = median - 1
- else:
- left_index = median + 1
- return("Error")
- def test(array, sort_method, find_method):
- time1 = time.time()
- for i in range(10):
- find_method(sort_method(array), random.randint(0, 10))
- time2 = time.time()
- return(time2-time1)
- print(f'Челночная сортировка и бинарный поиск 100 раз: {test(array, chelnok, binary)}с')
- print(f'Сортировка шелла и бинарный рекурсивный поиск 100 раз: {test(array, Shell, binary_recurs)}с')
- print(f'Быстрая сортировка и бинарный поиск по 100 раз: {test(array, quicksort, binary)}с')
- print(f'Сортировка центрированной вставкой и интерполяционный поиск по 100 раз: {test(array, insertion_sort, interpolation)}c')
Advertisement
Add Comment
Please, Sign In to add comment